Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

HOJOBOROLO, a multinational company, has $N$ employees numbered from $1$ through $N$. Each employee, except for lower-level employees, has at least one subordinate. Lower-level employees have no subordinate. Each employee, except for the head of the company, has **exactly one direct supervisor**. Employee number $1$ is the head of the company and he is in the highest level. There are $N$ teams in the company and employee number $i$ leads the $i$-th team. The $i$-th team consists of **the team leader** (employee number $i$) and all the direct or indirect subordinates of the team leader.

Now, there will be $Q$ projects this year for the company. The head will distribute all the projects among the teams. One project will not be given to more than one group.

After completing a project, all the team members associated with the project will get a bonus amount which will be added to their account. If employee number $X$ is a **team leader** then he/she will get a $2Y$ bonus amount and **other team members** will get a bonus amount of $Y$.

You have to tell the final account balance for each employee at the end of this year.

The first line contains an integer $T(1 \leq T \leq 10)$, the number of test cases.

The second line contains two integers $N(1 \leq N \leq 5\cdot 10^5 )$ and $Q (1\leq Q \leq N)$, the number of employees and the number of projects.

The third line contains $N$ integers $A_1, A_2, …, A_N (1 \leq A_i \leq 10^3)$, where $A_i$ is the initial account balance of employee number $i$.

Then each of the $N-1$ lines contain two integers $u ( 1 \leq u \leq N )$ and $v (1 \leq v \leq N)$, **where there is a connection between** $u$ **and** $v$ **and the connection represents the relation between supervisor and subordinate.**

The next $Q$ lines describe about the project distribution. In each line there are two integers $X (1 \leq X \leq N)$ and $Y (1 \leq Y \leq 5000)$, the $X$-th team for this project and bonus amount for each subordinates.

It is guaranteed that sum of $N$ over all test cases will not be greater than $5\cdot 10^5$.

For each test case, print $N$ integers in a line, the final (at the end of the year) account balance of each employee number from $1$ through $N$ respectively.

Input | Output |
---|---|

1 6 3 1000 1000 1000 1000 1000 1000 1 2 1 3 1 4 3 6 3 5 1 2000 4 3000 3 1500 | 5000 3000 6000 9000 4500 4500 |

After each query, update of the account balance of each employee is given below (Here, each node represents the corresponding employee and his/her current account balance is written nearby) $-$

85% Solution Ratio

Sharif_11Earliest,

Minus_XFastest, 0.3s

Uosmoy383Lightest, 54 MB

Zobayer_AbedinShortest, 816B

Login to submit

Prerequisites: Breadth First Search / Depth First Search Explanation: At first lets see two observat...