One Piece#10889
The Goa Kingdom is a network of islands (identified by numbers from to ), 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 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 islands. Initially, you can assume that each of the islands independently had a 50
The first line contains (1 \le n \le 250000), the number of islands. The following n - 1 lines describe the bridges. Each bridge connects two distinct islands. Finally, the last line contains 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 , 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.
Example 1
Example 2