Description

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.

Input Format

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

Output Format

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

2
1 2
3
4 

3/1 

5
1 2
2 4
1 3
5 2
2
1
1
1 
3 

1/2 

Hint

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 CONTEST #1 T4 Mag.

Translated by ChatGPT 5