Subtree queries - MarisaOJ: Marisa Online Judge

Subtree queries

Time limit: 1000 ms
Memory limit: 256 MB
You are given a tree of $n$ vertices rooted at $1$. Each vertex has a number written on it, initially $0$. There are $q$ queries, each of the form $(i, x)$, increasing each vertex in the subtree $i$ by $x$. Find the number on each vertex after $q$ queries. ### Input - The first line contain 2 integers $n$. - The next $n - 1$ lines, each line contains 2 integers $u$ and $v$, there is an edge between $u$ and $v$. - The next $q$ lines, each line contains 2 integers $u, x$, a query. ### Output - Print $n$ integers, the $i^{th}$ integers is the number on vertex $i$ after $q$ queries. ### Constraints - $1 \le n, q \le 10^5$. - $1 \le u, v, i \le n$. - $1 \le x \le 10^9$. ### Example Input: ``` 5 2 1 2 1 3 3 4 3 5 3 2 1 1 ``` Output: ``` 1 1 3 3 3 ``` _Note: There exists another solution beside using Euler tour. Try to find it!_