P6287 [COCI 2016/2017 #1] Mag

You will be given a tree connected by undirected edges. Each node in the tree has a magic value. We define the magic value of a path as the product of the magic values of all nodes on the path divided by the number of nodes on the path. For example, if a path contains two nodes with magic values $3,5$, then the magic value of this path is $3\times 5/2=7.5$. Please compute the magic value of the path with the smallest magic value in this tree.

The first line contains an integer $n$, indicating that the tree has $n$ nodes, numbered $1\dots n$. The next $n-1$ lines each contain two integers $a_i,b_i$, indicating that nodes $a_i$ and $b_i$ are connected by an undirected edge. The next $n$ lines each contain an integer $x_i$, indicating the magic value of node $i$.

Print one line containing a reduced fraction $p/q$.

#### Sample Explanation **Sample 1 Explanation** Note that a path may contain only one node. In this tree, the path with the smallest magic value contains node $1$, and its magic value is $3/1$. **Sample 2 Explanation** In this tree, the path with the smallest magic value contains nodes $2,4$, and its magic value is $1\times 1/2=1/2$. ------------ #### Constraints For $100\%$ of the testdata, $1\le n\le 10^6$, $1\le a_i,b_i\le n$, $1\le x_i\le 10^9$. It is guaranteed that $p,q$ will not exceed $10^{18}$. ------------ #### Notes **This problem is translated from [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #1](https://hsin.hr/coci/archive/2016_2017/contest1_tasks.pdf) _T4 Mag_.** Translated by ChatGPT 5