Description

Given a tree $T=(V,E)$, where $V$ is the set of nodes and $E$ is the set of edges.

For each node $v \in V$, there is a weight function $W(v)$ whose values are positive integers.

Let $d(u,v)$ be the distance between nodes $u$ and $v$, meaning the number of edges on the unique path between them. If $u$ and $v$ are the same node, then $d(u,v)=0$.

Your task is to find two distinct nodes $x$ and $y$ that minimize the following expression:

$$S(x,y)=\sum_{v\in V} (W(v)\cdot \min\{ d(v,x),d(v,y)\})$$

Input Format

• The first line contains $N$ ($1 < N \le 5\times 10^4$), the number of nodes in the tree. The nodes are numbered from $1$ to $N$.
• The next $N-1$ lines each contain two integers $U, V$, indicating there is an edge between $U$ and $V$.
• Then $N$ more lines follow. Each line contains a positive integer; on the $i$-th of these lines, the integer gives the weight $W(i)$ of node $i$.
• It is guaranteed that the depth of the tree does not exceed $100$.

Output Format

Output the minimal value of $S(x,y)$. The result is guaranteed not to exceed $10^9$.

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

14

Hint

In the sample, the two chosen centers are nodes $2$ and $3$.

Translated by ChatGPT 5