BZPRO

#2870. 最长道路tree

内存限制：512 MiB 时间限制：2 Sec
提交 提交记录 讨论

题目描述

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

输入格式

第一行N
第二行N个数分别表示1~N的点权v[i]
接下来N-1行每行两个数x、y，表示一条连接x和y的边
 

输出格式

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

样例

样例输入


			
3

5 3 5

1 2

1 3

样例输出


			
10

 

【样例解释】

选择从1到3的路径，痛苦程度为min(5,5)*2=10

数据范围与提示

100%的数据n<=50000

其中有20%的数据树退化成一条链

所有数据点权<=65536

Hint：建议答案使用64位整型

BZPRO Powered by Remmina.
Github Repository