Problem Description

There is a graph which is a tree with $n$ vertices, where each edge is an undirected edge of length $1$ in the form $(u, v)$.

You have a treasure detector. When you are at vertex $i$, it returns the maximum distance $x$, indicating that there is a treasure at a position at most $x$ units away from vertex $i$. A graph may have multiple treasures.

Given the results of the treasure detector for each vertex $i$ where $1 \leq i \leq n$, you are asked to determine the array of probabilities that each vertex contains a treasure, sorted from highest to lowest probability.

Input Format

The first line contains an integer $n\ (1 \leq n \leq 2.5 \times 10^5)$, representing the number of vertices.

The next $n-1$ lines each contain two integers $u, v$, representing an edge.

The next line contains $n$ numbers, representing the results of the treasure detector for each vertex $i$.

Output Format

Output the array of probabilities that each vertex contains a treasure, sorted from highest to lowest probability.

In case of equal probabilities, sort by vertex index in ascending order.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3 4 5 1 2

Sample Input #2

4
2 1
3 2
3 4
1 0 1 2

Sample Output #2

2 1 3 4

见题面 Input 部分

见题面 Output 部分