题目描述

给定一棵 $n$ 个节点的树，树上每个点有点权 $x_i$。
对于一条路径 $i_1,i_2,\cdots ,i_k$，定义路径的权值 $w$ 为

$$\frac{x_{i_1} \times x_{i_2} \times \cdots\times x_{i_k}}{k}$$

现在要找一条权值最小的路径，输出路径的权值，以分数的形式输出。

输入格式

第一行包括一个整数 $n$。
第二行到第 $n$ 行每行两个整数 $x,y$（$1\le x,y\le n$），表示一条 $x$ 到 $y$ 的树边。
第 $n+1$ 行到第 $2n$ 行，依次为 $x_1,x_2,\cdots, x_n$。

输出格式

输出答案的分数形式，形如 $a/b$，其中 $a,b$ 互质且为正整数。

样例

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

1/3

数据范围与提示

$n\le 500000$
$1\le x_i\le 10^7$