Qb
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
问题描述
给定一棵带点权的树，对于树上的一条路径，设路径包含的点数为P ，路径上的最大点权为Max ，最小点权为Min。请找一条路径使得P-Max+Min最小，输出这个最小值。
Input
第一行输入一个整数N 表示树的点数。
接下来一行N 个整数ai 表示 i 号点的权值。
接下来N− 1对整数xi , yi 表示xi , yi 之间存在一条边
Output
输出一个数表示最小值。
Examples
输入样例1:
5
2 1 4 4 1
3 2
1 2
5 2
4 5
输出样例1:
-1
输入样例2:
5
2 3 3 3 1
1 4
5 1
5 3
3 2
输出样例2:
0
输入样例3:
6
5 1 1 6 4 5
2 5
1 6
4 3
3 1
5 1
输出样例3:
-3
Notes
前 60%的测试数据满足N≤ 1000 ;
全部测试数据满足1 ≤ N ≤ 10^6 , 1 ≤ai≤ 10^9
