Recovering the Populations

Time limit4sMemory limit256 MB

Summary

Given a tree and the distance-weighted sums at each node, recover the node weights that produce them.

Level: Hard8 of 10
Topics: Tree, DFS, Math
Solved: No attempts yet

Problem

Byteasar is preparing a problem for a programming contest. He has already written a draft of the statement.

Byteotia has $n$ cities joined by $n - 1$ two-way roads, laid out so that the road network lets you travel between any two cities. Driving the road between two directly connected cities takes one hour. The cities are numbered from $1$ to $n$ , and $a_i$ inhabitants live in city $i$ .

An election is held in Byteotia next year. To keep full control over the vote, the king of Byteotia decided that the vote takes place in a single city. Every inhabitant of Byteotia travels to the city with the ballot box along a shortest route and votes there. All that is left is to choose the city that holds the vote, and this choice depends on many factors. In particular, for every city $i$ we want to compute the total time all inhabitants of Byteotia need to reach city $i$ . Call this value $b_i$ . [...]

Byteasar had already prepared unusually hard tests for the problem, but he accidentally lost half of the data. All that is left of each test is the part describing the roads and the output file with the values $b_i$ . From that alone Byteasar wants to recover the number of inhabitants of every city of Byteotia.

Input

The first line contains an integer $n$ ( $2 \le n \le 300000$ ), the number of cities in Byteotia. Each of the next $n - 1$ lines contains two integers $x_i$ , $y_i$ ( $1 \le x_i, y_i \le n$ ) describing one road, which means that city $x_i$ and city $y_i$ are joined by a road. The road network connects all cities.

The next line contains a sequence of $n$ integers $b_i$ ( $0 \le b_i \le 10^9$ ).

Output

Print a sequence of $n$ integers $a_i$ on one line, separated by single spaces. The number $a_i$ is the number of inhabitants of city $i$ of Byteotia. Solving Byteasar's problem for the printed sequence $a_i$ has to give back the sequence $b_i$ from the input.

The input always admits an answer. Once the road network and the sequence $b_i$ are fixed, only one sequence $a_i$ satisfies the condition, so print that sequence.

Examples5

Example 1
Input
```
2
1 2
17 31
```
Expected output
```
31 17
```
Example 2
Input
```
2
2 1
0 0
```
Expected output
```
0 0
```
Example 3
Input
```
3
1 2
2 3
10 7 4
```
Expected output
```
2 0 5
```

Example 4

Input

5
4 3
5 3
2 3
3 1
28 30 12 32 14

Expected output

2 1 8 0 9

Example 5

Input

8
4 5
8 3
6 7
4 1
4 3
5 7
3 2
132 183 128 89 94 168 121 189

Expected output

11 5 6 11 11 9 10 2