#bzoj3068. 小白树

小白树

题目背景

小白家门前有一颗小白树,树上的每个节点u都有一个权值W(u)W(u)。

小白树的奇特之处在于树上有两个不同的中心点xx和yy。

这两个中心点满足F(x,y)=∑min⁡[Dis(u,x),Dis(u,y)]×W(u)F(x,y)=\sum \min[Dis(u,x),Dis(u,y)]\times W(u)最小,其中DisDis表示两个节点的距离。

通俗地讲,就是对于每个节点uu,求出G(u)G(u)表示它到xx的距离和到yy的距离中间小的那个乘以它的权值。

那么所有G(u)G(u)的和就是F(x,y)F(x,y)。

现在小白想让你找出这两个中心点。你只需要输出F(x,y)F(x,y)就可以了。

输入格式

第一行有一个整数NN,NN表示小白树的节点个数。

之后N−1N-1行每行有两个整数aa和bb表示aa和bb之间有一条边。

之后NN行每行有一个整数,第ii个整数表示W(i)W(i)。

输出格式

一个整数表示F(x,y)F(x,y)。

样例

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

数据范围与约定

总共1010个测试点:

对于100%100\%的数据:2≤n≤5000000≤w≤100002\le n\le 500000 0\le w\le 10000