P9669 [ICPC 2022 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. 结束过程 ``` ------------

无

无