题目背景

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

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

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

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

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

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

输入格式

第一行有一个整数$N$，$N$表示小白树的节点个数。

之后$N-1$行每行有两个整数$a$和$b$表示$a$和$b$之间有一条边。

之后$N$行每行有一个整数，第$i$个整数表示$W(i)$。

输出格式

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

样例

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

14

数据范围与约定

总共$10$个测试点:

对于$100\%$的数据：$2\le n\le 500000 0\le w\le 10000$