AT_agc068_d.[AGC068D] Sum of Hash of Lexmin

有一棵以 $1$ 为根、包含 $N$ 个顶点的有根树 $T$，顶点编号为 $1$ 到 $N$。顶点 $1$ 是根，对于每个 $2 \leq i \leq N$，顶点 $i$ 的父节点为 $P_i$（$P_i < i$）。

对于 $1$ 到 $N$ 的一个排列 $x=(x_1,x_2,\cdots,x_N)$，判断它是否为良好排列的方法如下：

• 对于排列 $x$，可以进行如下操作：
  • 选择排列中相邻的两个元素 $u,v$，如果 $u,v$ 在树 $T$ 上存在祖先-子孙关系（无论谁是祖先谁是子孙均可），则可以交换 $u,v$ 的位置。
• 如果经过若干次（可以为 $0$ 次）上述操作，能够得到一个字典序严格小于初始排列的排列，则 $x$ 不是良好排列。否则，$x$ 是良好排列。

给定正整数 $B$。对于排列 $x$，定义 $\operatorname{hash}(x)=\sum_{1 \leq i \leq N} B^{i-1} \times x_i$。

请计算所有良好排列 $x$ 的 $\operatorname{hash}(x)$ 之和，并对 $998244353$ 取模后输出。

数列的字典序定义如下：设 $S=(S_1,S_2,\ldots,S_{|S|})$，$T=(T_1,T_2,\ldots,T_{|T|})$，则 $S$ 的字典序小于 $T$ 当且仅当满足以下两条之一：

1. $|S| < |T|$ 且 $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$。
2. 存在整数 $1 \leq i \leq \min\lbrace |S|,|T| \rbrace$，使得
   • $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$，
   • $S_i < T_i$。

输入为一行，格式如下：

$N$ $B$ $P_2$ $P_3$ $\cdots$ $P_N$

输出答案。

数据范围

• $2 \leq N \leq 100$
• $1 \leq B < 998244353$
• $1 \leq P_i < i$（$2 \leq i \leq N$）
• 输入的所有值均为整数

样例解释 1

例如，$x=(3,1,2)$ 不是良好排列。因为可以交换 $3,1$（它们在树上有祖先-子孙关系），得到 $x=(1,3,2)$，其字典序更小。在本样例中，良好排列为 $x=(1,2,3)$ 和 $x=(1,3,2)$ 共 $2$ 个。因此，$\operatorname{hash}((1,2,3))+\operatorname{hash}((1,3,2))=30201+20301=50502$，输出 $50502$。

样例解释 2

在本样例中，任意两个顶点都存在祖先-子孙关系。因此，唯一的良好排列为 $x=(1,2,3,4,5)$。

由 ChatGPT 4.1 翻译