← 返回题目列表

AtCoder · abc459_e

E. 从子树中选择

中文机器翻译题面 查看原题

分数: 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.