洛谷题单指南-树与图上的动态规划-P1352 没有上司的舞会

原题链接：https://www.luogu.com.cn/problem/P1352

题意解读：在一棵树中选择一些点，使得拥有最大的权值和，限制条件是选择一个点时不能选择其父节点。

解题思路：

如果由于所选择节点的最大权值和是一个状态，而这个状态可以由所有子树的状态推导出来，因此可以从树形DP的角度来思考该问题。

对于以u为根节点的树，u本身选与不选也是一种状态，将影响子树的选择。

1、状态表示

设f[u][0]表示u的子树中不选u的最大权值和，f[u][1]表示u的子树中选u的最大权值和

2、状态转移

对于u的所有子节点v，

不选u时，子节点v可以选或不选，所以有f[u][0] += max(f[v][0], f[v][1])
选u时，子节点只能不选，所以有f[u][1] += f[v][0]
3、初始化

f[u][0] = 0

f[u][1] = w[u]

4、结果

max(f[root][0], f[root][1])

100分代码：

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

const int N = 6005;
int f[N][2]; // f[u][0]表示u的子树中不选u的最大权值，f[u][1]表示u的子树中选u的最大权值
vector<int> g[N];
int n;
int w[N]; //快乐指数
bool fa[N]; //标记是否有父节点

void dfs(int u, int fa)
{
    f[u][0] = 0; //不选u的最大快乐指数
    f[u][1] = w[u]; //选u的最大快乐指数

    for(int v : g[u])
    {
        if(v == fa) continue; //避免回到父节点
        dfs(v, u); //递归处理子节点

        f[u][0] += max(f[v][0], f[v][1]); //不选u时，子节点可以选或不选
        f[u][1] += f[v][0]; //选u时，子节点只能不选
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i];
    }
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[v].push_back(u);
        fa[u] = true; //标记u有父节点
    }

    int root = 0;
    for(int i = 1; i <= n; i++)
    {
        if(!fa[i]) //找到没有父节点的节点，即根节点
        {
            root = i;
            break;
        }
    }

    dfs(root, 0);
    cout << max(f[root][0], f[root][1]); //输出根节点的最大快乐指数
    return 0;
}