#P13105. [AGC063E] Child to Parent

    ID: 12289 传统题 4000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000树形DP组合数学多项式动态规划数学

[AGC063E] Child to Parent

题目描述

有一棵有 NN 个顶点的有根树,顶点编号为 11 到 NN。顶点 11 是根,顶点 ii(2≤i≤N2\leq i\leq N)的父节点是 PiP_i。

给定一个非负整数 rr 和一个非负整数列 A=(A1,…,AN)A = (A_1, \ldots, A_N)。你可以对这个数列进行任意次(也可以不进行)如下操作:

  • 选择一个满足 i≥2i \geq 2 且 Ai≥1A_i \geq 1 的 ii。将 AiA_i 变为 Ai−1A_i - 1,并将 APiA_{P_i} 变为 APi+rA_{P_i} + r。

请你求出,最终可能得到的不同非负整数列 AA 的个数,答案对 998244353998244353 取模。

输入格式

输入以如下格式从标准输入给出。

NN P2P_2 …\ldots PNP_N rr A1A_1 …\ldots ANA_N

输出格式

输出最终可能得到的不同非负整数列 AA 的个数,对 998244353998244353 取模。

输入输出样例 #1

输入 #1

3
1 1
2
1 1 1

输出 #1

4

输入输出样例 #2

输入 #2

3
1 2
1
1 1 1

输出 #2

5

输入输出样例 #3

输入 #3

3
1 2
2
1 1 1

输出 #3

6

输入输出样例 #4

输入 #4

5
1 1 3 3
2
0 1 0 1 2

输出 #4

48

输入输出样例 #5

输入 #5

5
1 1 3 3
123456789
1 2 3 4 5

输出 #5

87782255

说明/提示

限制条件

  • 2≤N≤3002 \leq N \leq 300
  • 1≤Pi≤i−11 \leq P_i \leq i-1(2≤i≤N2 \leq i \leq N)
  • 0≤r≤1090 \leq r \leq 10^9
  • 0≤Ai≤1090 \leq A_i \leq 10^9

样例解释 1

最终可能得到的 AA 有以下 44 种:(1,1,1)(1,1,1)、(3,0,1)(3,0,1)、(3,1,0)(3,1,0)、(5,0,0)(5,0,0)。

样例解释 2

最终可能得到的 AA 有以下 55 种:(1,1,1)(1,1,1)、(1,2,0)(1,2,0)、(2,0,1)(2,0,1)、(2,1,0)(2,1,0)、(3,0,0)(3,0,0)。

样例解释 3

最终可能得到的 AA 有以下 66 种:(1,1,1)(1,1,1)、(1,3,0)(1,3,0)、(3,0,1)(3,0,1)、(3,2,0)(3,2,0)、(5,1,0)(5,1,0)、(7,0,0)(7,0,0)。