消防站

某座城市有 $N$ 个区域，编号为 $1$ 到 $N$ 。这些区域之间由 $N-1$ 条道路相连，且任意两个区域之间均存在路径。

每个区域 $i$ 都有一个正整数权值 $W(i)$ 。记 $d(u,v)$ 为区域 $u$ 与区域 $v$ 之间唯一路径所包含的边数。若 $u=v$ ，则 $d(u,v)=0$ 。

现在需要选择两个不同的区域建立消防站。对于两个不同的区域 $x$ 和 $y$ ，定义：

S(x,y)=\sum_{i=1}^{N}W(i)\min\{d(i,x),d(i,y)\}.

每个区域均由距离它较近的消防站提供服务。请选择区域 $x$ 和 $y$ ，使得 $S(x,y)$ 最小。

输入格式

输入共 $N+1$ 行。

第一行包含一个正整数 $N$ ，表示区域数量。

接下来 $N-1$ 行，每行包含两个整数 $u$ 、 $v$ ，表示区域 $u$ 与区域 $v$ 之间有一条道路。

最后一行包含 $N$ 个正整数，其中第 $i$ 个正整数表示区域 $i$ 的权值 $W(i)$ 。

输出一个非负整数，表示 $S(x,y)$ 的最小值。

选择区域 $2$ 和区域 $3$ 建立消防站，此时 $S(2,3)=14$ 。

本题题面与测试数据整理自 BZOJ。