← 返回题目列表

AtCoder · awc0099_c

C. 浇水

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

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