21914번 - One Piece 다국어

The Goa Kingdom is a network of $n$ islands (identified by numbers from $1$ to $n$), connected by $n - 1$ bidirectional bridges. The network is structured as a tree. Some islands contain valuable treasures, and Luffy is on a quest to find the treasures from all islands.

In order to ease the treasure hunting, he bought a detector from a local merchant. The detector should have shown the distance from each island to the closest treasure (in number of bridges); however, it seems to be horribly broken, and shows the distance from each island to the farthest treasure instead!

Nonetheless, he kept the distances that his broken detector showed for each of the islands, hoping that maybe not everything is lost. He now wonders which islands have a higher chance of containing a treasure.

Your task is to help Luffy by arranging the $n$ islands in order, from highest to lowest probability of containing a treasure, given that he now knows the distances shown by the detector for each of the $n$ islands. Initially, you can assume that each of the islands independently had a $50\%$ chance of containing a treasure; in other words, every subset of islands was equally likely to be the subset of the treasure islands.

The first line of the input contains $n$ ($1 \le n \le 250\,000$), the number of islands. The following $n - 1$ lines describe the bridges. Each bridge connects two distinct islands. Finally, the last line contains $n$ non-negative integers, the distances (in number of bridges) shown on Luffy’s detector for each of the islands.

It is guaranteed that there is at least one non-empty subset that is consistent with the input data.

Output a permutation of size $n$, the order of the islands from highest to lowest probability of containing a treasure. If two islands have the same probability of containing a treasure, output them in increasing order of their ids.

In the first example, island $3$ must contain a treasure, as it is the only one at distance $2$ from island $2$. Islands $4$ and $5$ have probability $2/3$ each, while islands $1$ and $2$ have probability $1/2$.

In the second example, the only possible scenario is that island $2$ is the only one containing a treasure.