#P1084. 【UR #34】死亡回归
【UR #34】死亡回归
从这里开始吧,从第一开始——不,从零开始!

时间线本该没有分叉,但是 Subaru 的权能【死亡回归】让它分叉成了一棵外向树,深度越深代表时间节点越靠后,时间线则成为了树上的某一条祖孙链。
树上的每个叶子节点都是一个结局,而在众多的结局中有若干个是 Subaru 心目中的 Happy End(HE),其余都是 Bad End(BE)。如果 Subaru 沿着某条时间线走到了 BE,那么就会根据该结局的震撼程度进行对应次数的【死亡回归】倒退时间回到之前的某个时间点。
你作为命运的引路人,需要给每个 BE 结局指定震撼程度,让 Subaru 在不走重复边的情况下无论怎么走都能够到达 HE。
给你一颗 $N$ 个节点的外向树(树边是有向边,由父亲连向儿子),$1$ 号节点为根,并给你一个点集 $S$,保证 $S$ 内点都是叶子(没有出度的点)。
你需要给 $S$ 内节点之外的所有叶子 $i$ 一个正整数 $k_i$,设 $i$ 的 $k_i$ 级祖先是 $j$($k_i$ 级祖先指从当前节点开始向根走 $k_i$ 条边到达的节点),如果不存在 $k_i$ 级祖先则非法,否则加入一条由 $i$ 连向 $j$ 的有向边。建好图之后进行如下操作:
- Subaru 初始位于 $1$ 号节点,接下来每次从当前节点的所有未走过的出边中任意挑选一条,标记为已走过并走到该出边指向的节点,如果当前节点不存在未走过的出边,则把该节点记为终点。
一个合法的 $k$ 数组是好的,当且仅当按照该数组建出来的图执行上述操作后,无论中间过程如何选择,终点必为 $S$ 内节点。
你需要计数满足上述条件的好的 $k$ 数组的个数,对 $998244353$ 取模。
你可以认为 $k$ 数组中不是叶子的 $i$ 以及在 $S$ 内的 $i$ 的 $k_i=0$。
输入格式
本题单个测试点有多组测试数据。
设 $S$ 的大小为 $\left| S \right|$。
第一行一个正整数 $T$ 表示数据组数。
接下来,对于每组数据有:
第一行两个正整数 $N,\left| S \right|$。
接下来一行 $N-1$ 个数,第 $i$ 个数 $p_i$ 代表节点 $i+1$ 的父亲。
接下来一行 $\left| S \right|$ 个数表示 $S$ 内的数。
输出格式
对于每组数据,输出一行一个整数表示答案,对 $998244353$ 取模。
3
4 1
1 2 1
4
6 1
1 2 3 3 2
6
8 1
1 2 3 3 4 4 2
8
1
3
11
下列数组下标从 $1$ 开始。
第一组数据中合法的 $k$ 数组只有一个:$\left[0,0,2,0\right]$。
第二组数据中合法的 $k$ 数组有以下三个:$\left[0,0,0,1,2,0\right],\left[0,0,0,2,1,0\right],\left[0,0,0,2,2,0\right]$。
2
10 3
1 2 3 3 2 6 6 2 1
4 8 10
20 1
1 1 2 3 4 6 3 2 4 6 9 8 9 7 12 12 16 14 15
19
17
99
1
40 5
1 1 1 2 5 3 5 2 9 9 8 8 9 13 11 15 11 17 13 15 13 20 16 18 16 13 16 21 21 23 18 23 30 22 26 31 22 27 30
4 24 29 32 38
736948674
数据范围
本题采用捆绑测试。
设 $\sum N$ 为单个测试点内所有 $N$ 的和。
对于 $100\%$ 的数据,保证:
- $1 \le \left| S \right| < N \le 8000,1 \le T,\sum N \le 3.2 \times 10^4$。
- $1 \le p_i < i+1$。
| 子任务编号 | 分值 | $N \le$ | $\sum N \le$ | 特殊性质 |
|---|---|---|---|---|
| $1$ | $5$ | $10$ | $100$ | 无 |
| $2$ | $15$ | $500$ | $2000$ | 有 |
| $3$ | $10$ | $2500$ | $10^4$ | |
| $4$ | $20$ | $8000$ | $3.2 \times 10^4$ | |
| $5$ | $15$ | $500$ | $2000$ | 无 |
| $6$ | $10$ | $2500$ | $10^4$ | |
| $7$ | $25$ | $8000$ | $3.2 \times 10^4$ |
特殊性质 :$\left| S \right|=1$。
时间限制:$\texttt{2s}$
空间限制:$\texttt{512MB}$