有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？

输入格式


第一行包含一个整数 n 。

接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。

接下来一共 n-1 行，每行描述树上的一条边。

输出格式

输出一个整数，代表选出的点的权值和的最大值。

样例输入

5
 1 2 3 4 5
 1 2
 1 3
 2 4
 2 5

样例输出

12

样例说明

选择3、4、5号点，权值和为 3+4+5 = 12 。

数据规模与约定


对于20%的数据， n <= 20。

对于50%的数据， n <= 1000。

对于100%的数据， n <= 100000。

权值均为不超过1000的正整数。

求详细点的解题算法，谢谢.

校内oj的练习题，

怎么没人来说呢。

好吧，我上oj看看，还是beyondyf 版主好，看你的程序，学到很多东西，

这是测评结果，全部数据通过，
评测点序号

评测结果

得分

CPU使用

内存使用

下载评测数据

1 正确 10.00 0ms 3.820MB VIP特权
 2 正确 10.00 0ms 3.820MB VIP特权
 3 正确 10.00 0ms 3.820MB VIP特权
 4 正确 10.00 0ms 3.839MB  
 5 正确 10.00 0ms 3.820MB  
 6 正确 10.00 109ms 3.820MB  
 7 正确 10.00 93ms 3.820MB  
 8 正确 10.00 93ms 7.355MB  
 9 正确 10.00 109ms 5.960MB  
 10 正确 10.00 109ms 7.875MB

嗯，谢谢版主啦，你是个顶尖的知识分子，有什么会不信任呢，