该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

0x50 动态规划（0x54 树形DP）例题1：没有上司的舞会

没有上司的舞会

题目描述

给出一棵有 $n$ 个点的有根树，第 $i$ 个点的权值为 $w_i$。

选出某些点，使得所选点的权值和最大。

要求有边直接相连的两点不能同时选。

输入格式

第一行一个整数 $n \ (1\leq n \leq 6 \times 10^3)$。

下来 $n$ 个整数 $w_i \ ( |w_i| \leq 127)$。

下来 $n-1$ 行，每行一对整数 $x \ y$，表示一条从点 $x$ 到 $y$ 的有向边。

输出格式

一行一个整数，代表最大权值和。

样例输入

7
1 1 1 1 1 1 1
1 3
2 3
6 4
7 4
4 5
3 5

样例输出

5