P1352 Party Without a Boss

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.

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 a single line with one integer representing the maximum total happiness index.

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