#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}$