U397527 BZOJ2870 最长道路tree

H 城很大，有 $N$ 个路口（从 $1$ 到 $N$ 编号），路口之间有 $N-1$ 条边，使得任意两个路口都能互相到达，这些道路的长度我们视作一样。 每个路口都有很多车辆来往，所以每个路口 $i$ 都有一个拥挤程度 $v_i$，我们认为从路口 $s$ 走到路口 $t$ 的痛苦程度为 $s$ 到 $t$ 的路径上拥挤程度的最小值，乘上这条路径上的路口个数所得的积。 现在请你求出痛苦程度最大的一条路径，你只需输出这个痛苦程度。 简化版描述： 给定一棵 $N$ 个点的树，求树上一条链使得链的长度乘链上所有点中的最小权值所得的积最大。 其中链长度定义为链上点的个数。

第一行一个数 $N$。 第二行 $N$ 个数分别表示 $1 \sim N$ 的点权 $v_i$。 接下来 $N-1$ 行每行两个数 $x,y$，表示一条连接 $x$ 和 $y$ 的边。

一个数，表示最大的痛苦程度。

### 样例解释 选择 $1 \to 3$ 的路径，痛苦程度为 $\min(5,5)\times2=10$。 ### 数据范围与提示 对于 $100\%$ 的数据 $n\le5\times10^4,0\le v_i\le65536$。 对于 $20\%$ 的数据，树退化成一条链。 Hint：建议答案使用 $64$ 位整型。