题目描述

给定一棵 $n$ 个点的树，求树上一条链使得链的长度乘链上所有点中的最小权值所得的积最大。

其中链长度定义为链上点的个数。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $v_{1\cdots n}$，表示每个点的点权。

接下来 $n-1$ 行每行两个数 $u,v$ 表示一条树上的边 $(u,v)$。

输出格式

一行一个整数表示答案。

3
5 3 5
1 2
1 3

10

样例分析

$1-2$ 这条链的长度乘以最小点权的结果是 $6$，$1-3$ 这条链的长度乘以最小点权的结果是 $10$，$2-1-3$ 这条链的长度乘以最小点权的结果是 $9$，所以答案是 $10$。

数据范围与提示

对于 $20\%$ 的数据，树的形态是一条链；

对于 $100\%$ 的数据，$1\le n\leq 5\times 10^4$，$1\le v_i\leq 65536$。