P2726 [SHOI2005] Double Center of a Tree

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)\}) $$

- 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 the minimal value of $S(x,y)$. The result is guaranteed not to exceed $10^9$.

In the sample, the two chosen centers are nodes $2$ and $3$. Translated by ChatGPT 5