【例题1】树上求和

题目描述

给出一个 $n$ 个结点的树，每个结点都有一个权值 $r_{i}$ ，请你选择一些结点，使得被选结点的权值和最大，且被选结点之间不能存在父子关系，即选了父亲不能选儿子，选了儿子不能选父亲。

输入的第一行是一个整数 $n$ 。

第 $2$ 行到第 $n+1$ 行，每行一个整数，第 $i+1$ 行的整数 $r_{i}$ 表示 $i$ 号节点的权值。

第 $n+2$ 到第 $2n+1$ 行，每行输入一对整数 $l$ , $k$ ，代表 $k$ 是 $l$ 的父亲。

输出一个整数，表示最大权值和。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 6 \times 10^{3}$ ， $-128 \leq r_{i} \leq 127$ ， $1 \leq l,k \leq n$ ，且给出的关系一定是一棵树。