4211. [SHOI2005] 树的双中心

【题目描述】

给定一棵树 $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_{v\in V} (W(v)\cdot \min\{ d(v,x),d(v,y)\})$$

【输入格式】

第一行为 $N\;(1<N\le5\times 10^4)$，表示树的节点数目，树的节点从 $1$ 到 $N$ 编号。

接下来 $N-1$ 行，每行两个整数 $U,V$，表示 $U$ 与 $V$ 之间有一条边。

再接下 $N$ 行，每行一个正整数，其中第i行的正整数表示编号为 $i$ 的节点权值为 $W(i)$。

保证树的深度不超过 $100$。

【输出格式】

将最小的 $S(x,y)$ 输出。

【样例输入】

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

【样例输出】

14

【样例说明】

样例中，选取的两个中心节点分别为 $2$ 和 $3$。

【数据规模与约定】

暂无数据

【来源】

SHOI2005。