P9669 [ICPC 2022 Jinan R] DFS Order 2

Prof. Pang has a rooted tree that is rooted at vertex $1$ and has $n$ nodes. These $n$ nodes are numbered from $1$ to $n$. Now he wants to start the depth-first search at the root. He wonders for each node $v$, how many ways it can appear in the $j$-th position of $\textbf{depth-first search order}$. The depth-first search order is the order of nodes visited during the depth-first search. A node appears in the $j$-th ($1\le j\le n$) position in this order means it is visited after $j-1$ other nodes. Because sons of a node can be iterated in arbitrary order, multiple possible depth-first orders exist. Prof. Pang wants to know for each node $v$, how many different $\textbf{depth-first search order}$s such that $v$ appears in the $j$-th position. For each $v, j~(1 \le v, j \le n)$, compute the answer. Because the answer can be very large, output it modulo $998244353$. Following is a pseudo-code for the depth-first search on a rooted tree. After calling $\textbf{main}$(), $\texttt{dfs\_order}$ is the depth-first search order. 

N/A

N/A