Problem Description

There is a graph, which is a tree with $n$ nodes. Each edge is an undirected edge of the form $(u,v)$ with length $1$.

You have a treasure detector. When you are at node $i$, it returns a farthest distance $x$, meaning that among all treasure locations that exist, the maximum distance from node $i$ to a node containing a treasure is $x$. A graph may contain multiple treasures.

Now you are given the detector’s returned results for all $1 \leq i \leq n$. Please output the array obtained by sorting all nodes in decreasing order of the probability that there is a treasure at that node.

Input Format

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

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

The next line contains $n$ numbers, where the $i$-th number is the return value of the treasure detector when called at node $i$.

Output Format

Output the array obtained by sorting all nodes in decreasing order of the probability that there is a treasure at that node.

If probabilities are equal, sort by node index in increasing order.

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

3 4 5 1 2

4
2 1
3 2
3 4
1 0 1 2

2 1 3 4

Hint

Translated by ChatGPT 5