19017번 - Automorphism 다국어

You are given a rooted tree. Initially, it contains one vertex labeled as $1$.

Your task is to process $m$ operations of two types:

• Add a new vertex to the tree.
• Calculate the number of automorphisms of the subtree rooted at vertex $u$.

As the numbers can be very large, find them modulo $998\,244\,353$.

For a rooted tree, whose root is $r$ and vertex set is $S$, the automorphism is a bijection $f: S \to S$ such that $f(r) = r$ and $\forall u, v \in S$, $f(u)$ is the parent of $f(v)$ if and only if $u$ is the parent of $v$.

The first line contains one integer $m$ ($1 \leq m \leq 3 \cdot 10^5$).

In the following $m$ lines, each line indicates an operation.
Each of these lines contains two integers $t$ and $x$ ($0 \leq t \leq 1$).

If $t = 0$, add a new vertex labeled by the current maximum label plus $1$. Add an edge between this new vertex and the vertex $x$.

If $t = 1$, calculate the number of automorphisms of the subtree of vertex $x$.

It is guaranteed that, for each operation, the value of $x$ is between $1$ and the current maximum label.

For each calculate operation, print a single line with the number of automorphisms modulo $998\,244\,353$.