题目描述

给出一棵有根的树，树上有 $n$ 个顶点，编号为 $1$ 至 $n$ 。

根是顶点 $1$ ，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$ 。

每个顶点都有一个计数器。最初，所有顶点上的计数器的值都是 $0$ 。

现在将执行 $q$ 次操作：

• 第 $i$ 次操作：将以顶点 $p$ 为根的子树中包含的每个顶点的计数器递增 $x$ 。

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

输入格式

第一行输入两个空格隔开的整数 $n,q$。

接下来输入 $n-1$ 行每行输入两个整数 $a_i,b_i$。

接下来输入 $q$ 行每行输入两个整数 $p,x$。

输出格式

输出一行空格隔开 $n$ 个整数。

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

100 110 111 110

样例 1 解释

该输入的树形结构如下

每次操作都会改变顶点上计数器的值，具体如下：

• 操作 $1$ ：将以顶点 $2$ 为根的子树（即顶点 $2, 3, 4$ ）中包含的每个顶点的计数器的值增加 $10$ 。顶点 $1, 2, 3, 4$ 上计数器的值现在分别为 $0, 10, 10, 10$ 。
• 操作 $2$ ：将以顶点 $1$ （即顶点 $1, 2, 3, 4$ ）为根的子树中包含的每个顶点的计数器的值递增 $100$ 。顶点 $1, 2, 3, 4$ 上计数器的值现在分别为 $100, 110, 110, 110$ 。
• 操作 $3$ ：将以顶点 $3$ （即顶点 $3$ ）为根的子树中包含的每个顶点的计数器的值递增 $1$ 。顶点 $1, 2, 3, 4$ 上的计数器值现在分别为 $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

数据范围

• 对于 $30\%$ 的数据满足：$2\leq n\leq 10^3$，$1\leq q \leq 10^3$，$1\leq p\leq n$，$1\leq x\leq 10^4$。
• 对于 $100\%$ 的数据满足：$2\leq n\leq 2\times 10^5$，$1\leq q \leq 10^5$，$1\leq p\leq n$，$1\leq x\leq 10^4$。