没有上司的舞会

题意概述

1. 每一个点都有一个权值
2. 对于一个点i，如果选了它，那么它的儿子就不能选了。如果不选它，那么它的儿子可选可不选
3. 问怎么选，使得总权值和最大

思路

1. 对于一个点，如果它的父亲选了，那么它一定选不了
2. 如果它的父亲没有选，它就可以选也可以不选
3. 那到底选还是不选---选一个最有利的情况
4. 那么每个点就有两种状态了：选或不选
5. 用标识不选，标识选
6. 不选i点时，i点及其子树能选出来的最大价值 选i点时，i点及其子树能选出来的最大价值
7. 那么最终结果就是
8. 状态转移：对于点不选，那么它的儿子可选可不选，
   对于点选了，那么它的儿子就不能选了，
9. 边界情况：对于叶子节点

代码

// 没有上司的舞会
#include <bits/stdc++.h>
#define endl '\n'
// #define int long long
using lli = long long;
using ull = unsigned long long;
inline int read()
{
    int x = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            flag = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * flag;
}

int val[6004];
int dp[6004][2];
std::vector<int> t[6004];
void dfs(int s, int fa)
{
    dp[s][0] = 0, dp[s][1] = val[s]; // 每个点的初始条件，顺带把边界也处理了
    for (int i = 0; i < t[s].size(); i++)
    {
        int j = t[s][i];
        if (j == fa) continue;
        dfs(j, s);
        dp[s][0] += std::max(dp[j][0], dp[j][1]);
        dp[s][1] += dp[j][0];
    }
}

signed main()
{
    int n = read();
    for (int i = 1; i <= n; i++)
    {
        val[i] = read();
    }
    int u = 0, v = 0;
    for (int i = 1; i <= n - 1; i++)
    {
        u = read(), v = read();
        t[u].push_back(v);
        t[v].push_back(u);
    }
    dfs(1, 0);
    std::cout << std::max(dp[1][0], dp[1][1]);
    return 0;
}