分数: 450 点
问题陈述
有一棵有根的树 T 与 N 顶点,其中顶点编号为 vertex 1,顶点 2, \ldots,顶点 N.
顶点 1 是根 T,以及顶点的(直接)父级 i (2 \leq i \leq N) is P_i.
另外,顶点 i (1 \leq i \leq N) 有 C_i 糖果。 全部 (C_1 + C_2 + \cdots + C_N) 糖果彼此不同。
高桥指示 N 松鼠。 具体来说,他给了以下指示: i-第松鼠 (1 \leq i \leq N):
- 选择并收集 D_i 来自以顶点为根的子树的糖果 i.
不同的松鼠不能吃相同的糖果。
输出数字,模数 998244353,选择糖果的可能方法。
这里,即使最终选择的糖果组是相同的,如果选择它们的松鼠不同,它们也会被算作不同的方式。
如果不可能按照指示让所有松鼠都带回糖果,则输出 0.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq P_i \leq N
- 1 \leq C_i \leq 10^9
- 1 \leq D_i
- D_1 + D_2 + \cdots + D_N \leq 10^6
- 所有输入值均为整数。
- T 是一棵有顶点的有根树 1 作为根。
输入
输入由标准输入按以下格式给出:
N P_2 P_3 \ldots P_N C_1 C_2 \ldots C_N D_1 D_2 \ldots D_N
输出
输出数字,模数 998244353,选择糖果的可能方法。
示例输入 1
5 1 1 3 3 1 2 1 2 3 1 1 3 1 1
示例输出 1
144
我们打电话给糖果,这样我们就有糖果了 1 在顶点 1, 糖果 2, 3 在顶点 2, 糖果 4 在顶点 3, 糖果 5, 6 在顶点 4和糖果 7, 8, 9 在顶点 5.
选择糖果的一种可能的方法如下:
- 松鼠 1 收集糖果 3 来自以顶点为根的树 1 (由顶点组成 1, 2, 3, 4, 5).
- 松鼠 2 收集糖果 2 来自以顶点为根的树 2 (由顶点组成 2).
- 松鼠 3 收集糖果 仅 4, 7, 9 来自以顶点为根的树 3 (由顶点组成 3, 4, 5).
- 松鼠 4 收集糖果 6 来自以顶点为根的树 4 (由顶点组成 4 )。
- 松鼠 5 收集糖果 8 来自以顶点为根的树 5 (由顶点组成 5 )。
请注意,这与以下的计算方式不同:
- 松鼠 1 收集糖果 \mathbf{2} 来自以顶点为根的树 1 (由顶点组成 1, 2, 3, 4, 5).
- 松鼠 2 收集糖果 \mathbf{3} 来自以顶点为根的树 2 (由顶点组成 2).
- 松鼠 3 收集糖果 仅 4, 7, 9 来自以顶点为根的树 3 (由顶点组成 3, 4, 5).
- 松鼠 4 收集糖果 6 来自以顶点为根的树 4 (由顶点组成 4 )。
- 松鼠 5 收集糖果 8 来自以顶点为根的树 5 (由顶点组成 5 )。
有 144 总共有效的方法,所以输出 144 模数 998244353,即 144.
示例输入 2
2 1 1 1 2 1
示例输出 2
0
树的顶点只有两颗糖果 1 和 2,所以两只松鼠不可能按照指示收集糖果。
因此,输出 0.
示例输入 3
3 3 1 1000000000 1 1 1 1 1
示例输出 3
1755647
记住输出计数模数 998244353.