Description

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.

Input Format

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 Format

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

3
1 2 3
1 2
1 3

1

Hint

Constraints

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