题目描述
给定一棵以 号点为根的树，树上有 个点，第 个点有一个权值 。
你需要选出若干个点（可以一个也不选），满足：如果点 被选中，且 ，那么 的父亲也必须被选中。
设选中的点集为 ，求 的最大值。
输入格式
第一行一个整数 。
第二行 个整数 。
接下来 行，每行两个整数 ，表示树上的一条边。
输入保证给出的边构成一棵树，且以 号点为根。
输出格式
一行一个整数，表示最大权值和。
样例 1
输入：
6
5 -3 4 -2 6 -7
1 2
1 3
2 4
3 5
3 6
输出：
15
样例说明：以 为根时， 号点的孩子是 ， 号点的孩子是 。选择 ，权值和为 ，满足“选了孩子就必须选父亲”。可以证明不存在更优方案。
数据范围
| 子任务 | 分值占比 | |
|---|---|---|
| 1 | 20% | |
| 2 | 30% | |
| 3 | 50% |
对于全部数据，，。