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$ после добавления каждой вершины.

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