Pty with card

An upsurge in a card game has swept across Pty Town. As a Mayor of the town, Pty is certainly curious about the game and about to organize a large-scale game in his town. The game is played in this rule:

1. N participants stand in a circle, and everyone has one card in hand.
2. Choose one randomly to take the lead in Round 1.
3. In Round i, let’s assume that it’s Steve’s turn and Tom is standing next to him at the clockwise. Then Tom will take cards from Steve. If i is odd, he takes 1, otherwise 2. And if at this time Steve has no card left, he is considered ’out’ and quits the circle, keeping others in the original order. In Round i + 1, it comes to Tom’s turn.
4. Anytime there’s only one participant left, the game is over.

Obviously there’s some values of N making the game constant. So for those N, we define the ’Circle’ of the game with N participants - F(N). That means, F(N) equals to the minimized T so that there exists an i , for all j ≥ i + T, there are uniform participants and each has uniform number of cards in Round j and Round j-T. Particularly, if the game will be over with N original participants, F(N) = 0.

Pty Town is composed of M cities. We can reach arbitrary cities from each city through M-1 paths. We use ($x_i$,$y_i$) to describe the $i^{th}$ path, which connects City $x_i$ and City $y_i$. Formally, we have dist(x,y) represent the distance between City x and City y. Pty figures out that, a route from City x to City y to be chosen for the game, the number of the participants p(x,y) equals to $v_x$ + dist(x,y). For City x, Pty wants to know the summation of ’Circle’ when he choose all the routes ending with City x. Namely, for each x, you should tell him $\sum_{j=1}^n$$F(p(j,x))$ .

You are given the value of M, $v_i$,$x_i$ and $y_i$, you should tell Pty the answer.

T testcases in total. T is given in the first line. (1 ≤ T ≤ 10)

For each testcase:

The first line contains a single positive integer M(1 ≤ M ≤ $10^5$) the number of the cities.

The second line contains M positive integers $v_i$ (1 ≤ $v_i$ ≤ $10^5$).

Each of the other M-1 lines contains two positive integers $x_i$,$y_i$, representing a path between City $x_i$ and City $y_i$.(1 ≤ $x_i$,$y_i$ ≤ M)

It is guaranteed that $\sum M$ ≤ $5 \times 10^5$.

There are T lines in total.

For each testcase, you should output M numbers in one line. The $i^{th}$ number means the answer to City i.

1
5
1 2 3 4 5
1 2
3 2
3 5
5 4

12 12 0 0 0

For the route (2,1) the number of the participants is 3.The game performs like this: (1,1,1) → (2,1) → (3) and the game is over. F(p(2,1)) = F(3) = 0.

For the route (5,1) the number of the participants is 8. The game performs like this: (1,1,1,1,1,1,1,1) → (2,1,1,1,1,1,1) → (3,1,1,1,1,1) → (2,2,1,1,1,1) →
...... (2,2,2,2) → (4,2,2) → (3,3,2) → (3,1,4) → (4,1,3) → (2,3,3) → (2,2,4) → (4,2,2) → (3,3,2) → ......

So F(p(5,1)) = F(8) = 6.

2021“MINIEYE杯”中国大学生算法设计超级联赛（10）