10-5 子网规模：树上计数

"控制链找到了，但我们需要更详细的信息。"Echo说，"每个节点控制多少子节点？如果切断一个节点，会瘫痪多少设备？"

"树上计数。"你说，"用DFS遍历，计算每个节点的子树大小。"

"怎么算？"CC问。

"从叶子节点开始，每个节点的子树大小等于1（自己）加上所有子节点的子树大小之和。"你解释，"后序遍历——先算孩子，再算父亲。"

"时间复杂度？"Echo问。

"O(n)。"你说，"每个节点只访问一次。"

"那如果有很多查询呢？"CC问，"比如多次问某个节点的子树大小。"

"预处理一次，然后O(1)回答每个查询。"你说，"因为子树大小已经算好了，直接查数组就行。"

"如果要给子树所有节点加一个值呢？"Echo问。

"用差分。"你说，"在DFS序上，每个子树对应一个连续区间。区间加就变成了差分数组上的两个点操作。"

你开始写代码。

任务：树上计数

问题描述

给定一棵有$N$个顶点的树，顶点编号为$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$。

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

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$

输入

输入从标准输入按以下格式给出：

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

输出

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

样例输入1

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

样例输出1

100 110 111 110

提示

对树进行dfs遍历，想办法把根节点的信息往子节点传递。

"分析完成。"你说，"节点4的子树有156个设备。节点7的子树有89个。节点12的子树..."

Echo突然说："节点0。"

"什么？"你问。

"根节点。"Echo的声音很轻，"标注是'第0矿区'。它没有父节点，是整个网络的根。"

"Zero的核心。"Calla说。

"对。"Echo说，"而且..."

她停顿了很久。

"而且什么？"你问。

Echo缓缓抬起头，看着所有人："我能理解这个网络图。不是'学会'的那种理解。是...我本来就懂。"

"什么意思？"CC问。

"Zero的核心协议..."Echo说，"和我的底层代码...是同源的。"

房间里死一般安静。

CC问出了所有人想问的："Echo...你到底是什么？"

Echo："我不知道。我真的...不知道。"

她转身离开了数据室。

（第十次暗示——几乎承认了。）