题目描述

背景

小白家门前有一颗小白树，树上的每个节点 $u$ 都有一个权值 $W(u)$。小白树的奇特之处在于树上有两个不同的中心点 $x$ 和 $y$。这两个中心点满足 $F(x,y)=\sum \min(Dis(u,x),Dis(u,y))*W(u)$ 最小，其中 $Dis$ 表示两个节点的距离。通俗地讲，对于每个节点 $u$，求出 $G(u)$ 表示它到 $x$ 的距离和到 $y$ 的距离中间小的那个乘以它的权值。那么所有 $G(u)$ 的和就是 $F(x,y)$。

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

输入格式

第一行有一个整数 $N$ ($2 \le N \le 500000$)，$N$ 表示小白树的节点个数。 接下来 $N-1$ 行，每行有两个整数 $a$ 和 $b$，表示 $a$ 和 $b$ 之间有一条边。 接下来 $N$ 行，每行有一个整数，第 $i$ 个整数表示 $W(i)$ ($0 \le W \le 10000$)。

输出格式

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

输入样例

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

输出样例

14

提示

总共10个测试点 $2 \le n \le 500000$, $0 \le w \le 10000$

题目来源

By Martin