A92839.最小路径价值

现在有一棵包含 $n$ 个顶点的树。顶点编号为 $1$ 到 $n$，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$ ，第 $i$ 个顶点的权值为 $w_i$ 。

现在定义 $d(a, b)$ 为顶点 $a$ 和 $b$ 之间的边数。对于 $x = 1, 2, \ldots, N$，定义 $x$ 的路径价值

$$f(x) = \sum_{i=1}^{n} (w_i \times d(x, i))$$

请你求出 $\displaystyle \min_{1 \leq v \leq n} f(v)$ 的值，即最小路径价值。

第一行输入一个整数 $n$ $(1\leq n\leq 10^5)$ ，表示树上顶点的个数。

接下来 $n-1$ 行，每行两个整数 $u_i,v_i$ $(1\leq u_i,v_i\leq n)$ ，表示 $u_i$ 和 $v_i$ 之间有一条边。

第 $n+1$ 行，输入 $n$ 个整数 $w_i$ $(1\leq w_i\leq 10^9)$，表示第 $i$ 个顶点的权值。

输出一个这个数，表示 $\displaystyle \min_{1 \leq v \leq N} f(v)$ 的值。

样例解释 1

以 $f(1)$ 为例，$d(1, 1) = 0, d(1, 2) = 1, d(1, 3) = 1, d(1, 4) = 2$。因此，

$$f(1) = 0 \times 1 + 1 \times 1 + 1 \times 1 + 2 \times 2 = 6$$

同理，$f(2) = 5, f(3) = 9, f(4) = 6$。$f(2)$ 最小，所以输出 5。

样例解释 2

$f(2) = 1$，这是最小值。