#3302. [Shoi2005]树的双中心

内存限制:128 MiB 时间限制:10 Sec

题目描述

输入格式

第一行为N,1<N<=50000,表示树的节点数目,树的节点从1到N编号。
接下来N-1行,每行两个整数U,V,表示U与V之间有一条边。
再接下N行,每行一个正整数,其中第i行的正整数表示编号为i的节点权值为W(I),
树的深度<=100

输出格式

将最小的S(x,y)输出,结果保证不超过19^9

样例

样例输入


			
5
1 2
1 3
3 4
3 5
5
7
6
5
4

样例输出


			
14

数据范围与提示

选取两个中心节点为2,3