Home

Contest: Task: Related: TaskC TaskE

Score : $400$ points

Problem Statement

Given is a rooted tree with $N$ vertices numbered $1$ to $N$. The root is Vertex $1$, and the $i$-th edge $(1 \leq i \leq N - 1)$ connects Vertex $a_i$ and $b_i$.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value $0$.

Now, the following $Q$ operations will be performed:

  • Operation $j$ $(1 \leq j \leq Q)$: Increment by $x_j$ the counter on every vertex contained in the subtree rooted at Vertex $p_j$.

Find the value of the counter on each vertex after all operations.

Constraints

  • $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$
  • The given graph is a tree.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the values of the counters on Vertex $1, 2, \ldots, N$ after all operations, in this order, with spaces in between.

Sample Input 1

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

Sample Output 1

100 110 111 110

The tree in this input is as follows:

Figure

Each operation changes the values of the counters on the vertices as follows:

  • Operation $1$: Increment by $10$ the counter on every vertex contained in the subtree rooted at Vertex $2$, that is, Vertex $2, 3, 4$. The values of the counters on Vertex $1, 2, 3, 4$ are now $0, 10, 10, 10$, respectively.
  • Operation $2$: Increment by $100$ the counter on every vertex contained in the subtree rooted at Vertex $1$, that is, Vertex $1, 2, 3, 4$. The values of the counters on Vertex $1, 2, 3, 4$ are now $100, 110, 110, 110$, respectively.
  • Operation $3$: Increment by $1$ the counter on every vertex contained in the subtree rooted at Vertex $3$, that is, Vertex $3$. The values of the counters on Vertex $1, 2, 3, 4$ are now $100, 110, 111, 110$, respectively.

Sample Input 2

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

Sample Output 2

20 20 20 20 20 20