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

5

#include<bits/stdc++.h>
using namespace std;

/*
洛谷 P1352 没有上司的舞会
题意：
    有 n 个人，每个人有一个快乐值 a[i]。
    给出 n-1 条上下级关系，形成一棵树。
    要求：如果一个人参加舞会，那么他的直接上司不能参加。
    求参加舞会的人快乐值之和的最大值。

做法：
    树形 DP。
    设：
        f[x][0]：以 x 为根的子树中，x 不参加舞会时的最大快乐值
        f[x][1]：以 x 为根的子树中，x 参加舞会时的最大快乐值
    转移：
        f[x][0] = sum(max(f[y][0], f[y][1]))
        f[x][1] = a[x] + sum(f[y][0])
    其中 y 是 x 的下属。
*/

int n, a[6005];

// 邻接表存边
// head[x]：以 x 为起点的第一条边的编号
// ver[i]：第 i 条边指向的节点
// Next[i]：第 i 条边的下一条边编号
int ver[6005], Next[6005], head[6005], tot;

// f[x][0]：x 不参加舞会时，以 x 为根的子树最大快乐值
// f[x][1]：x 参加舞会时，以 x 为根的子树最大快乐值
int f[6005][2], x, y;

// fa[i] = true 表示 i 有上司，不是整棵树的根
bool fa[6005];

// 添加一条从 x 指向 y 的有向边
// 这里表示 x 是 y 的上司，x -> y
void add(int x, int y)
{
    ver[++tot] = y;      // 当前边指向 y
    Next[tot] = head[x]; // 当前边的下一条边是原来 head[x] 指向的边
    head[x] = tot;       // head[x] 更新为当前边
}

// 树形 DP，x 是当前子树的根
void dp(int x)
{
    // 初始化：
    // x 不参加，当前贡献为 0
    f[x][0] = 0;

    // x 参加，先算上自己的快乐值
    f[x][1] = a[x];

    // 遍历 x 的所有下属 y
    for(int i = head[x]; i; i = Next[i])
    {
        int y = ver[i];

        // 先递归处理以 y 为根的子树
        dp(y);

        // 如果 x 不参加，那么下属 y 可以参加，也可以不参加
        // 取两种情况的最大值
        f[x][0] += max(f[y][0], f[y][1]);

        // 如果 x 参加，那么下属 y 不能参加
        // 只能加上 f[y][0]
        f[x][1] += f[y][0];
    }
}

int main()
{
    // 读入人数
    scanf("%d", &n);

    // 读入每个人的快乐值
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    // 读入 n-1 条上下级关系
    // 输入 x y 表示：y 是 x 的上司
    for(int i = 1; i < n; i++)
    {
        scanf("%d %d", &x, &y);

        // 注意：y 是 x 的上司
        // 所以从 y 向 x 连一条有向边，表示 y -> x
        add(y, x);

        // x 有上司，所以 x 不是根
        fa[x] = 1;
    }

    // 找到没有上司的节点，也就是整棵树的根
    for(int i = 1; i <= n; i++)
    {
        if(!fa[i])
        {
            // 从根开始树形 DP
            dp(i);

            // 根节点可以参加，也可以不参加，取最大值
            printf("%d", max(f[i][0], f[i][1]));

            // 题目保证是一棵树，只有一个根，找到后直接结束
            break;
        }
    }

    return 0;
}