[ICPC2022 Jinan R] DFS Order 2

### 题目描述 P有一棵树，根节点是$1$，总共有$n$个节点，从$1$到$n$编号。 他想从根节点开始进行深度优先搜索。他想知道对于每个节点$v$，在深度优先搜索中，它出现在第$j$个位置的方式有多少种。深度优先搜索的顺序是在搜索过程中访问节点的顺序。节点出现在第$j（1 \le j \le n $）个位置表示它在访问了$j - 1$个其他节点之后才被访问。因为节点的子节点可以以任意顺序访问，所以有多种可能的深度优先搜索顺序。 P想知道对于每个节点$v$，有多少种不同的深度优先搜索顺序，使得$v$出现在第$j$个位置。对于每个$v$和$j（i \le v,j \le n）$，计算答案。答案可能很大，所以输出时要取模$998244353$。以下是深度优先搜索的伪代码，用于处理树。在调用$main()$函数后， dfs_order将会包含深度优先搜索的顺序。 ------------ #### 算法 $1$ 深度优先搜索的实现 ``` 1. 过程 DFS(节点 x) 2. 将x添加到dfs_order的末尾 3. 对于x的每个子节点y do ·子节点可以以任意顺序遍历。 4. DFS(y) 5. 结束循环 6. 结束过程 7. 过程 MAIN() 8. 将dfs_order设为全局变量 9. dfs_order ← 空列表 10. DFS(1) 11. 结束过程 ``` ------------ ### 输入格式 第一行包含一个整数$n（1\le n\le 500）$，表示树中的节点数量。 接下来的n-1行描述了树的边。第i行包含两个整数$u_i$和$v_i$，表示连接的两个节点的标签$（1\le u_i,v_i\le n,u_i\not=v_i）$。 保证给定的边构成一棵树。 ### 输出格式 对于每个从$1$到$n$的节点$v$，输出一行，包含$n$个整数，取模$998244353$。在第$v$行中，第$j$个整数表示不同的深度优先搜索顺序中，节点$v$出现在第$j$个位置的数量。 翻译由@ayf2192538031提供

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. 

The first line contains one integer $n~(1\le n \le 500)$, the number of vertices in the tree. Each of the next $n-1$ lines describes an edge of the tree. Edge $i$ is denoted by two integers $u_i$ and $v_i$, the labels of vertices it connects $(1\le u_i,v_i\le n, u_i\neq v_i)$. It is guaranteed that the given edges form a tree.

For each vertex $v$ from $1$ to $n$, output one line containing $n$ integers modulo $998244353$. The $j$-th integer in the $v$-th line should be the number of different depth-first search orders such that $v$ appears in the $j$-th position.

5
1 2
1 3
3 4
3 5

4 0 0 0 0
0 2 0 0 2
0 2 2 0 0
0 0 1 2 1
0 0 1 2 1