P7130 "RdOI R1" Balance Constant (balance).

Given a rooted weighted tree $G=(V,E)$ with root $1$, the weight of node $i$ is denoted by $w_i$. Let the set of nodes in the subtree rooted at $i$ be $V_i$. Find a node set $V'\subseteq V$ that satisfies the following conditions: - For all $i$, $|V_i \cap V'| \le \lfloor \frac{|V_i|}{2} \rfloor$. - Maximize $\sum _{i \in V'} w_i$. You only need to output $\sum _{i\in V'} w_i$, i.e., the sum of the weights of the selected nodes.

The first line contains a positive integer $n$. The second line contains $n$ positive integers $w_i$. The next $n-1$ lines each contain two integers $u,v$, representing the two endpoints of an edge.

Output a single line containing the maximum total sum you computed.

Constraints | Test Point ID | $n\leq$ | $w_i\leq$ | Special Property | | - | - | - | - | | $1\sim2$ | $10$ | $10^3$ | | | $3\sim 5$ | $2 \times 10^3$ | $10^3$ | | | $6\sim12$ | $10^5$ | $10^3$ | | | $13\sim16$ | $5 \times 10^5$ | $10^9$ | $v=u+1$ | | $17\sim25$ | $5 \times 10^5$ | $10^9$ | | For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^5$, $0 < w_i \leq 10^9$, $1 \leq u,v \leq n$. --- Notes / Hints - Idea From: LCuter. --- File Input/Output **(simulation, not needed when submitting code)** - File name: `balance.cpp`. - Input file name: `balance.in`. - Output file name: `balance.out`. Translated by ChatGPT 5