题目描述

给定一棵树 $T=(V,E)$，其中 $V$ 为节点集合，$E$ 为边集合，对于 $V$ 中的每个节点 $v$，有一个权值函数 $W(v)$，该函数的值均为正整数，记 $d(u,v)$ 为节点 $u$ 和 $v$ 之间的距离，表示他们之间唯一的一条路径的边数。若 $u$ 和 $v$ 为同一个节点，则 $d(u,v)=0$。你的任务是找出两个不同的节点 $x,y$，使得以下表达式 $S(x,y)$ 最小：

$$S(x,y)=\sum\limits_{v\in V}(W(v)\times \min(d(x,v),d(y,v))). $$

输入格式

第一行为 $n$，表示树的节点数目，树的节点从 $1$ 到 $n$ 编号。
接下来 $n-1$ 行，每行两个整数 $u,v$，表示 $u$ 与 $v$ 之间有一条边。
再接下 $n$ 行，每行一个正整数，其中第 $i$ 行的正整数表示编号为 $i$ 的节点权值为 $w_i$。

输出格式

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

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

14

样例说明 1

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

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 5\times 10^4$，保证树的深度 $\le 100$。