Ural 大学有 NN 名职员，编号为 1∼N1∼N。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 HiHi 给出，其中 1≤i≤N1≤i≤N。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

第一行一个整数 NN。

接下来 NN 行，第 ii 行表示 ii 号职员的快乐指数 HiHi。

接下来 N−1N−1 行，每行输入一对整数 L,KL,K，表示 KK 是 LL 的直接上司。

输出格式

输出最大的快乐指数。

数据范围

1≤N≤60001≤N≤6000,
−128≤Hi≤127−128≤Hi≤127

输入样例：

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

输出样例：

5

 学到了一个表示双链表的新方法：

vector数组表示双链表。

vector<int>  son[N] 相当于一个二维数组。

垂下来的帘子。

状态表示： dp [ N ] [ 0 或 1 ]  表示当前编号 N的节点 在被选中或是没被选中的情况下，其子树的最大开心值。

状态计算：　dp[x][1] += dp[y][0];（选中状态）
       　　　　 dp[x][0] += max(dp[y][0], dp[y][1]);（没被选中状态）；

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 6010;

int fa[N], happy[N]; // fa数组用于表示是否有父节点。
// 用于寻找根节点。
int dp[N][2];  // 用 0， 1 两个整数表示状态。

int n;

vector<int> son[N];// vector数组表示双链表。
// 学到了学到了， 双链表居然还可以用vector数组表示。

void dfs(int x)
{
    dp[x][1] = happy[x]; // 搜到后的处理。
    dp[x][0] = 0;
    for(int i = 0; i < son[x].size(); i ++)
    {
        int y = son[x][i];
        dfs(y);
        dp[x][1] += dp[y][0]; // 深搜到底后的处理。
        dp[x][0] += max(dp[y][0], dp[y][1]);
    }
}

int main()
{
    cin.tie(0);
    std::ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> happy[i];
    for(int i = 1; i <= n - 1; i ++) 
    {
        int x, y;
        cin >> x >> y;
        son[y].push_back(x);
        fa[x] = 1;
    }
    int root = 0;
    for(int i = 1; i <= n; i ++)
    if(!fa[i]) 
    {
        root = i;
        break;
    }
    dfs(root);
    cout << max(dp[root][1], dp[root][0]) << endl;
}