[AtCoder | DP] D - Ki

문제 링크

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 performed:

Operation $j(1 \leq j \leq Q)$ : Increment by $x_j$ the counter on every vertex contrained 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 \lt b_i\leq N$
$1\leq p_j\leq N$
$1\leq x_j\leq 10^4$

Input

\boxed{ \begin{array}{l} N \quad Q \\ a_1 \quad b_1 \\ \vdots \\ a_{N-1} \quad b_{N-1} \\ p_1 \quad x_1 \\ \vdots \\ p_Q \quad x_Q \end{array} }

Solution

graph TD
    A((1)) --- B((2))
    B --- C((3))
    B --- D((4))

    class A,B,C,D node;