魔力之树

题目描述

你将获得一棵由无向边连接的树。树上每个节点都有一个魔力值。

我们定义，一条路径的魔力值为路径上所有节点魔力值的乘积除以路径上的节点数。

例如，若一条路径包含两个魔力值分别为$3$，$5$的节点，则这条路径的魔力值为$3 \times 5 / 2 = 7.5$。

请你计算，这棵树上魔力值最小的路径的魔力值。

输入格式

第一行一个整数$n$，表示树共有$n$个节点，编号为$1 \ldots n$。

接下来$n-1$行，每行两个整数$a_i$，$b_i$，表示编号为$a_i$，$b_i$的两个节点由一条无向边连接。

接下来$n$行，每行一个整数$x_i$，表示编号为$i$的节点的魔力值。

输出格式

一行，一个既约分数$p/q$。

数据范围与提示

• 对于$25\%$的数据，$1 \leq n \leq 1000$；
• 对于$35\%$的数据，$1 \leq n \leq 10000$；
• 对于$45\%$的数据，$1 \leq n \leq 50000$；
• 对于$100\%$的数据，$1 \leq n \leq 10^{6}$，$1 \leq a_{i}$，$b_{i} \leq n$，$1 \leq x_{i} \leq 10^{9}$。

数据保证，$p$，$q$不会超过$10^{18}$。

样例

2
1 2
3
4

3/1

说明

注意，路径可以只包含一个节点。

这棵树上魔力值最小的路径的包含节点$1$，其魔力值为$3/1$。

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

1/2

说明

这棵树上魔力值最小的路径的包含节点$2$，$4$，其魔力值为$1 \times 1 / 2 = 1/2$。