分数: 366 分
问题陈述
高桥是植物园的管理员。植物园有 N 植物,编号自 1 to N。这些植物以树状结构进行管理,形成一棵有根的树,植物 1 作为根。
对于每个工厂 i (2 \leq i \leq N),工厂 P_i 是植物的亲本 i.
每种植物都有一个称为 水分含量,并且每株植物的水分水平最初为 0.
高桥表演 Q 浇水作业。在 j第一次操作 (1 \leq j \leq Q),他增加了以 plant 为根的子树中所有植物的湿度水平 X_j by D_j。在这里,子树以 plant 为根 X_j 是由植物组成的集合 X_j 本身和植物的所有后代 X_j.
确定每个植物的水分含量 Q 浇水作业已进行。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
- 1 \leq X_j \leq N (1 \leq j \leq Q)
- 1 \leq D_j \leq 10^9 (1 \leq j \leq Q)
- 所有输入值均为整数。
输入
N Q P_2 P_3 \ldots P_N X_1 D_1 X_2 D_2 \vdots X_Q D_Q
- 第一行包含一个整数 N 代表植物数量和一个整数 Q 代表浇水操作的次数,以空格分隔。
- 第二行包含 N - 1 整数 P_2, P_3, \ldots, P_N 以空格分隔,代表植物的亲本 2 通过 N. P_i 是植物的亲本编号 i。当 N = 1,该行上没有写入任何内容(给出了空行)。
- 下一个 Q 行从第三行开始,给出了浇水操作的详细信息。的 (2 + j)- 第行包含工厂编号 X_j 的目标 j第次浇水操作及水分增加量 D_j,用空格分隔。
输出
输出 N 单行上用空格分隔的整数。的 i-th 值应该是植物的水分水平 i 执行完所有浇水操作后。
示例输入 1
5 2 1 1 2 2 1 10 2 5
示例输出 1
10 15 10 15 15
示例输入 2
7 3 1 1 2 2 3 3 3 20 1 5 5 100
示例输出 2
5 5 25 5 105 25 25
示例输入 3
10 4 1 2 3 3 3 1 7 7 9 1 3 3 7 7 2 9 10
示例输出 3
3 3 10 10 10 10 5 5 15 15