Ki

题目描述

给出一棵以顶点 $1$ 为根的树，顶点编号为 $1$ 到 $N$。 根是顶点 $1$，第 $i$ 条边 $(1 \leq i \leq N - 1)$ 连接顶点 $a_i$ 和 $b_i$。 每个顶点上都装有一个计数器。起初，所有顶点上的计数器的值均为 $0$。 现在将进行以下 $Q$ 次操作：

操作 $j$ $(1 \leq j \leq Q)$：将位于以顶点 $p_j$ 为根的子树内的每个顶点的计数器增加 $x_j$。

求所有操作完成后每个顶点上的计数器的值。

输入格式

从标准输入按如下格式给出输入： $N$ $Q$ $a_1$ $b_1$ : $a_{N-1}$ $b_{N-1}$ $p_1$ $x_1$ : $p_Q$ $x_Q$

输出格式

按顺序输出所有操作完成后顶点 $1, 2, \ldots, N$ 上计数器的值，顶点之间用空格分隔。

4 3
1 2
2 3
2 4
2 10
1 100
3 1

100 110 111 110

6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10

20 20 20 20 20 20

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq Q \leq 2 \times 10^5$ 1 \leq a_i < b_i \leq N $1 \leq p_j \leq N$ $1 \leq x_j \leq 10^4$ 给定的图是树。 输入中的所有值均为整数。该输入对应的树如下所示： 每次操作对计数器值的变化如下所示：

操作 $1$：将以顶点 $2$ 为根的子树内的每个顶点的计数器增加 $10$，即顶点 $2, 3, 4$。此时顶点 $1, 2, 3, 4$ 上的计数器的值分别为 $0, 10, 10, 10$。 操作 $2$：将以顶点 $1$ 为根的子树内的每个顶点的计数器增加 $100$，即顶点 $1, 2, 3, 4$。此时顶点 $1, 2, 3, 4$ 上的计数器的值分别为 $100, 110, 110, 110$。 操作 $3$：将以顶点 $3$ 为根的子树内的每个顶点的计数器增加 $1$，即顶点 $3$。此时顶点 $1, 2, 3, 4$ 上的计数器的值分别为 $100, 110, 111, 110$。

标签: AtCoder|abc138D

来源

AtCoder|abc138D