最简单的树形DP模板 洛谷没有上司的舞会

https://www.luogu.com.cn/problem/P1352#submit

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

const int N = 10005;

struct edge {
    int nxt, to;
} edges[N];

int n;
int idx;
int head[N];
int r[N];       //每个节点的快乐数
int f[N][2];    //f[i][0]为不包含该节点 f[i][1]为包含

inline void add(int a, int b) 
{
    edges[++idx].to = b;
    edges[idx].nxt = head[a];
    head[a] = idx;
}

void dfs(int root) {
    for (int e = head[root]; e != 0; e = edges[e].nxt) {
        int to = edges[e].to;
        dfs(to);
        f[root][0] += max(f[to][0], f[to][1]);
        f[root][1] += f[to][0];
    }
    f[root][1] += r[root];
}

int main() 
{
#ifndef ONLINE_JUDGE
    freopen("D:/VS CODE/C++/in.txt", "r", stdin);
    freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
    cin >> n;

    unordered_set<int> root_set;

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &r[i]);
        root_set.insert(i);
    }

    for (int i = 1; i < n; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        add(b, a);
        root_set.erase(a);
    }

    int root = *root_set.begin();
    dfs(root);

    cout << max(f[root][0], f[root][1]);

    fclose(stdin);
    fclose(stdout);
    return 0;
}