题目描述

某个城市有 $n$ 个区域，这些区域用 $1$ 到 $n$ 这 $n$ 个正整数编号，并且它们之间通过 $n-1$ 条道路相连，保证任意两个区域有路径相通。对于每个区域 $i$,有一个正整数权值 $w_i$。记 $d_{u,v}$为区域 $u$ 和区域 $v$ 之间的距离，表示它们之间唯一的一条路径的边数。若 $u$ 和 $v$ 为同一个区域，则 $d_{u,v}=0$。

现在要选择两个区域建立消防站，你的任务是找出这两个不同的区域 $x$ 和 $y$ 使得 $S(x，y)$ 的值最小。

输入格式

共 N+1 行。 第一行有一个正整数 N ，表示区域的个数。 接下来有 N-1 行，每行两个整数 u 、 v ，表述区域 u 和区域 v 之间有一条道路。 最后一行有 N 个正整数，第 i 个正整数表示区域 i 的权值 W(i) 。

输出格式

包含一个正整数，为最小的 S(x, y) 的值。

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

14

提示

【样例解释】

选取区域2和区域3。

【数据规模和约定】

用H表示距离区域1最远结点的距离，即d(1, u)的最大值。

对于30%的数据满足：2 ≤ N ≤ 300

余下70%的数据满足：2 ≤ N ≤ 50000、H ≤ 70、W(i) ≤ 100

题目来源

2011福建集训