A6758. 「美团 CodeM 决赛」tree
编程题
普及/提高-
知识点
题目描述
给定一棵 $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} $$
现在要找一条权值最小的路径，输出路径的权值，以分数的形式输出。
对于一条路径 $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$。
第二行到第 $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$ 互质且为正整数。
输入输出样例
输入 #1
6 1 2 1 3 2 6 3 4 3 5 1 1 2 3 1 1
输出 #1
1/3
说明/提示
$n\le 500000$
$1\le x_i\le 10^7$
$1\le x_i\le 10^7$