CSP-J 二叉树专题原创训练。

题目描述

有 n 个节点组成一棵以 1 为根的二叉树，第 i 个节点的重要程度为 ai。

你可以选择若干节点安装守护装置，但任意两个存在直接父子关系的节点不能同时选择。

求所选节点重要程度之和的最大值。

输入格式

第一行 n。 第二行 n 个整数 a1...an。 接下来 n 行，第 i 行两个整数 Li Ri，表示左右孩子，不存在用 0 表示。

输出格式

输出最大重要程度总和。

样例

输入：

7
10 8 7 6 5 4 3
2 3
4 5
6 7
0 0
0 0
0 0
0 0

输出：

28

数据范围

1 <= n <= 200000，1 <= ai <= 10^9。 保证输入是一棵以 1 为根的二叉树。