28818번 - Случайное дерево 다국어

문제

Рассмотрим следующий процесс построения дерева $T$.

Изначально дерево состоит из одной вершины, которая имеет номер 1ドル$.

Дальше в дерево добавляются вершины с номерами 2ドル \ldots n$.

На $i$-м шаге в дерево добавляется вершина с номером $i+1,ドル также в дерево добавляется ребро из нее в некоторую уже добавленную вершину $p$ (1ドル \leq p \leq i$), которая выбирается среди них случайно равновероятно.

Пусть $V$ --- множество уже добавленных в $T$ вершин.

Тогда пусть $f(A)$ --- количество вершин $T,ドル что они лежат или в $A,ドル или на пути между какими-либо двумя вершинами из $A$ (возможно, и там, и там).

Ваша задача после добавления каждой вершины вывести сумму $f(A)$ по всем множествам $A,ドル которые являются подмножествами множества уже добавленных в $T$ вершин ($\sum{f(A)}$ по всем $A \subseteq V$). Так как ответы могут быть очень большим, выводите лишь остатки от деления ответа на 998244353ドル$.

입력

Первая строка входного файла содержит одно число $n$ --- количество вершин в дереве после последнего шага $(2 \leq n \leq 200000)$.

В следующей строке расположено $n-1$ целое число $p_1, p_2, \ldots, p_n$ (1ドル \leq p_i \leq i$), обозначающих добавления в граф вершины $i+1$ и ребра между $p_i$ и $i+1$ соответственно. Гарантируется, что $p_i$ выбрано случайно равновероятно среди чисел от 1ドル$ до $i$.

출력

Выведите $n-1$ целое число, остатки от деления ($\sum{f(A)}$ по всем $A \subseteq V$) на 998244353ドル$ после добавления каждой вершины.

제한

노트

Итоговые деревья из примеров: