战争 (war)

题目背景

——高中三年是一场战争，而在这冰冷的战场上，我们相依取暖。

打开一个个漂流瓶，安又看到了数不清的祝福，以及随信附上的资料。

就像往常所做的一样，他记下了自己所需。他知道，在他观看的同时，系统已经将漂流瓶复制了若干份，送进了广阔的数据海中，等待着下一个有缘的学生。

安很喜欢漂流瓶计划的主题：“知识与善意的指数式传递”。

被阅读得越多的漂流瓶便漂得越广，让本不相关的人们，在同样的年纪，并肩而战。

题目内容和题目背景有部分区别，请注意。同时注意，你可以阅读形式化题意。

安在自己的收件箱中看到了若干个同样种类的漂流瓶，上面的标题是：受战火波及，漂流瓶计划宣布破产。

惊讶的他发现今天是愚人节，而愚人节的玩笑是这样运作的：

第 $i$ 个人初始时会收到 $a_i$ 个完全一致的漂流瓶，安是第 $1$ 个人。

每个人都可以观看若干个漂流瓶，每看一个就会给一个特定的人 $p_i < i$ 送去 $k$ 个同样的漂流瓶。

最后有若干个漂流瓶送到安这里（可能为零），而他还没有看过任何一个漂流瓶（注意：虽然不合常理，但是他的信箱可能是空的）。

经过这样的过程之后，安想要知道，每个人的信箱中，没有被看过的漂流瓶的可能状态数。定义两个状态不同，当且仅当存在一个人信箱中没有被看过的漂流瓶的数量不同。答案对 $998244353$ 取模。

形式化题意：

给定一棵 $n$ 个点以 $1$ 为根的树，初始点有点权 $a_i$。

定义一次操作为选择一个 $a_u>0$ 的点，令 $a_u\gets a_u-1,a_{fa_u}\gets a_{fa_u}+k$。求任意次操作后可能得到的序列 $a$ 的数量。

对 $998244353$ 取模。

第一行两个正整数 $tid,T$ 表示测试数据编号和测试数据组数。

对于每组数据：第一行输入两个数 $n,k$ 表示人数的复制的倍数。

第二行输入 $n-1$ 个数，第 $i-1$ 个数表示 $p_i$。

第三行输入 $n$ 个数表示初始漂流瓶个数 $a$。

对于每组数据，输出一行一个数表示答案对 $998244353$ 取模后的结果。

0 2
3 2
1 1
0 1 1
3 998244352
1 2
0 1 1

4
3

对于第一组数据，第二和第三个人有没有看过漂流瓶决定了最终状态，因此答案为 $4$。

对于第二组数据，状态数为 $998244356$。

记 $V$ 为 $a_i$ 的最大值。测试数据满足：

数据点编号	$n\le$	$k\le$	$V$	特殊性质
$1,2$	$10$	$1$	$10$
$3$	$10$	$998244352$	$10^9$	A
$4$	$10$	$0$	$10^9$	C
$5$	$10$	$998244352$	$10^9$
$6,7$	$50$	$1$	$10$
$8$	$50$	$1$	$10^9$
$9$	$50$	$998244352$	$10$	A
$10$	$50$	$998244352$	$10^9$	A
$11$	$50$	$998244352$	$10^9$	B
$12$	$50$	$998244352$	$10$
$13$	$50$	$998244352$	$10^9$
$14,15$	$3\times10^2$	$1$	$10$
$16,17$	$3\times10^2$	$1$	$10^9$
$18$	$3\times10^2$	$998244352$	$10^9$	A
$19$	$3\times10^2$	$0$	$10^9$	C
$20$	$3\times10^2$	$998244352$	$10^9$	B
$21,22$	$3\times10^2$	$998244352$	$10$
$23,24,25$	$3\times10^2$	$998244352$	$10^9$