Treasure Hunt in Tree

You are given an undirected tree with (n) nodes where each edge has unit length. Every edge is denoted as ((u,v)). You also have a treasure detector. When you are at node (i), the detector returns a value (x_i) which represents the farthest distance from (i) to a treasure. Note that there may be multiple treasures in the tree.

A configuration is an assignment of treasures to some nodes (the configuration must be non‐empty) such that for every node (i), if we let (S) be the set of nodes with a treasure then (\max_{j \in S} ; d(i,j) = x_i) (where (d(i,j)) is the distance between (i) and (j)). Assume that all valid configurations (those that satisfy the detector readings for every node) are equally likely. Your task is to compute, for every node, the probability that a treasure is placed at that node. Finally, output the probabilities sorted in descending order.

All formulas in this description are in (\LaTeX) format.

inputFormat

The first line contains a single integer (n) representing the number of nodes. The next (n-1) lines each contain two integers (u) and (v) which denote an edge between node (u) and node (v). The last line contains (n) integers (x_1, x_2, \ldots, x_n) where (x_i) is the value returned by the treasure detector at node (i).

outputFormat

Output a single line with (n) space‐separated numbers. These numbers are the probabilities that each node contains a treasure (based on uniform probability among all valid configurations), sorted in descending order. Each probability should be printed with at least 6 decimal places.

sample

2
1 2
0 1

1.000000 0.000000