Description

A university has $n$ employees, numbered $1 \ldots n$.

There is a hierarchy among them, meaning their relationships form a tree rooted at the university president, where a parent node is the direct supervisor of its child nodes.

There will be an anniversary banquet. Inviting an employee increases the happiness index by $r_i$. However, if an employee’s direct supervisor attends the banquet, that employee will refuse to attend no matter what.

Please compute which employees to invite so that the total happiness index is maximized, and find the maximum total happiness index.

Input Format

The first line contains an integer $n$.

Lines $2$ to $(n + 1)$ each contain one integer. The integer on line $(i + 1)$ is the happiness index $r_i$ of employee $i$.

Lines $(n + 2)$ to $2n$ each contain a pair of integers $l, k$, meaning $k$ is the direct supervisor of $l$.

Output Format

Output a single line with one integer representing the maximum total happiness index.

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

5

Hint

Constraints

• For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 6 \times 10^3$, $-128 \leq r_i \leq 127$, $1 \leq l, k \leq n$, and the given relations form a tree.

Translated by ChatGPT 5