P10745 [SEERC 2020] One Piece

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.

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 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.

Translated by ChatGPT 5