Practice on Toph

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

Bonus Project

By maruf089 · Limits 1s, 256 MB

HOJOBOROLO, a multinational company, has NN employees numbered from 11 through NN. 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 11 is the head of the company and he is in the highest level. There are NN teams in the company and employee number ii leads the ii-th team. The ii-th team consists of the team leader (employee number ii) and all the direct or indirect subordinates of the team leader.

Now, there will be QQ 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 XX is a team leader then he/she will get a 2Y2Y bonus amount and other team members will get a bonus amount of YY.

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

Input

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

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

The third line contains NN integers A1,A2,,AN(1Ai103)A_1, A_2, …, A_N (1 \leq A_i \leq 10^3), where AiA_i is the initial account balance of employee number ii.

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

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

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

Output

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

Sample

InputOutput
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) -

    Discussion

    Statistics


    85% Solution Ratio

    Sharif_11Earliest, 4M ago

    Minus_XFastest, 0.3s

    Uosmoy383Lightest, 54 MB

    Zobayer_AbedinShortest, 816B

    Submit

    Login to submit

    Editorial

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

    Toph uses cookies. By continuing you agree to our Cookie Policy.