洛谷 P1352 没有上司的舞会

传送门

思路

一道入门的简单的树形\(DP\)题
我们用\(is\)数组来表示这个点是不是根节点
如果他有上司，就绝对不是根节点了
因为这是一棵树，所以只会有一个人没有上司，而他就是根节点
然后考虑如何进行\(DP\)，我们用\(f[x][0/1]\)表示只考虑以\(x\)点为根的子树，且\(x\)号点有/没有被选择，被选择的点的权值和的最大值。
令\(x\)点的儿子构成的集合为\(son_x\) ，转移考虑 \(x\)点选不选。
显然转移方程为
\[f[x][0] = \sum y∈son_x\ max(f[y][0],f[y][1])\]
\[f[x][1] = \sum y∈son_x\ f[y][0]\]
最后的答案为\(max{f(root,0),f(root,1)}\)//\(root\)就是根节点

代码

//知识点:树形DP
/*
By:Loceaner
*/
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    return x * f;
}

const int N = 6e3 + 11;

vector <int> e[N];
int ans;//ans记录答案
int n, f[N][2], is[N], vis[N];
//f[x][0/1]表示只考虑以 x 点为根的子树，且 x 号点有/没有被选择，被选择的点的权值和的最大值。
//is[i]用来判断是否为根节点，vis[i]表示是否访问过

void dfs(int x) {
    vis[x] = 1;
    for(int i = 0; i < (int)e[x].size(); i++) {
        int to = e[x][i];
        if(vis[to]) continue;
        dfs(to);
        f[x][1] += f[to][0];
        f[x][0] += max(f[to][0], f[to][1]);
    }
    return;
}

int main() {
    n = read();
    for(int i = 1; i <= n; i++) f[i][1] = read();//一开始输入的就是选i的快乐值
    for(int i = 1, l, k; i < n; i++) {
        l = read(), k = read();
        is[l] = 1;//肯定不是根节点
        e[k].push_back(l);
    }
    scanf("0 0");
    for(int i = 1; i <= n; i++) {
        if(!is[i]) {//is数组中没有被访问过的便是根节点
            dfs(i);
            ans = max(f[i][0], f[i][1]);
            cout << ans << '\n';
            return 0;
        }
    }
    return 0;
}