P6048 最优性剪枝

Nauuo 是一名出题人。 众所周知，某些出题人非常懒，导致[随便爆搜](https://www.luogu.com.cn/discuss/show/185420)加上一个[最优性剪枝](https://www.luogu.com.cn/discuss/show/184641)就能通过。Nauuo 决定把这些 naive 的暴力都卡掉。

Nauuo 决定卡一个暴力搜索程序，为此她构建了一组数据。为了简化题目，你将得到这组数据产生的搜索树 $T$。$T$ 中包含 $n$ 个节点，依次编号为 $1 \sim n$，其中 $1$ 号点是 $T$ 的根节点。一个节点的深度是它到 $1$ 号点的简单路径上的节点个数。 这个程序的伪代码如下 ```cpp answer := inf procedure dfs(node,depth) if (node is leaf) answer := min(answer,depth) return if (depth < answer) for i in children of node dfs(i,depth+1) dfs(1,1) ``` 其中，`:=` 表示赋值运算。 翻译成人话就是说，这个暴力搜索程序将**深度优先**地遍历这棵搜索树，当访问到一个叶节点时，这个程序将用这个叶节点的深度更新答案。 同时，这个程序有一个最优性剪枝，也就是说，当这个程序访问到任意一个深度等于答案的节点时，它将不会再访问这个节点的子节点。 然而，可怜的 Nauuo 并不知道这个程序在某个节点时访问自己子节点的顺序，因此她认为每个节点访问子节点的顺序都是在所有可能的情况中等概率随机的，显然，一共有 $\prod d_i!$ 种情况，其中 $d_i$ 表示 $i$ 号节点的子节点数量。 现在她想知道这个程序访问到的节点数量的期望，以确定这个程序会不会被自己的数据卡掉。 为了避免浮点误差，答案对 $998244353$ 取模。保证答案能被表示为最简分数 $\frac{p}{q}$，你只需要输出一个 $x (0\leq x < 998244353)$ 使得 $qx \equiv p \pmod {998244353}$。

无

无

#### 样例解释 第一组样例的真实答案为 $\frac{7}{2}$。 一共只有两种情况，如果 $1$ 号节点先遍历 $3$ 号节点，则程序将访问到搜索树中所有节点。如果 $1$ 号节点先遍历 $2$ 号节点，则 $4$ 号节点不会被访问到。 第二组样例中，每个非叶节点的子节点都是唯一的，因此只有一种可能的情况，所有节点都必然被访问到。 第三组样例的真实答案为 $\frac{94}{9}$。 --- #### 数据范围 **「本题采用捆绑测试」** 对于所有测试点，保证 $1 \leq n \leq 3\times 10^5$，$1 \leq p_i < i$。 $\text{Subtask 1 (11 pts)}$ $n \leq 9$。 $\text{Subtask 2 (18 pts)}$ $n \leq 100$。 $\text{Subtask 3 (19 pts)}$ $n\leq 10^3$。 $\text{Subtask 4 (4 pts)}$ $p_i = i-1$。 $\text{Subtask 5 (8 pts)}$ $p_i =\lfloor \frac{i}{2} \rfloor$。 $\text{Subtask 6 (40 pts)}$ 无特殊限制。 --- #### 提示 如果你不知道怎么对分数取模，可以参考[这里](https://www.luogu.com.cn/problem/P3811)。