6210. 「美团 CodeM 决赛」tree

传统 $1000$ ms $512$ MiB $62$ 通过 $153$ 提交

题目描述

给定一棵 $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$