树形dp基础

Fish_Chen · 2025-07-09 20:59:09 · 生活·游记

今天学习了树形dp依旧啥都没听懂

但是，我还是要水一篇博客：D

树形dp，顾名思义，是在树上dp。

以今天写的例题P1352 没有上司的舞会来讲。通过惊人的观察力，发现他是一道树形dp。所以我们首先要建树，于是：

for(int i = 1; i < n; ++i) {
    int l, k;
    cin >> l >> k;
    g[l].push_back(k);
    g[k].push_back(l);
}

很快就面临一个问题——没有根节点！ 我们知道，如果某人有上司，那么这个人一定是下属。所以我们只需要找出没有上司的人，就是他们的老总（即本题的根节点）。

于是我们可以用一个递归函数dfs来遍历每一个节点。

于是我们有了STD。

恩。

// 树形dp 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn (int)(6*(1e3)+10)
using namespace std;
int n;
int r[maxn], dp[maxn][2];
set<int> st;
vector<int> g[maxn];
void dfs(int now,int fa = -1) {
    dp[now][0] = 0;
    dp[now][1] = r[now];
    for(auto to : g[now]) {
        if(to == fa)
            continue;
        dfs(to, now);
        dp[now][0] += max(dp[to][0],    dp[to][1]);
        dp[now][1] += dp[to][0];
    }
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> r[i];
        st.insert(i);
    }
    memset(dp, 0xef, sizeof(dp));
    for(int i = 1; i < n; ++i) {
        int l, k;
        cin >> l >> k;
        g[l].push_back(k);
        g[k].push_back(l);
        st.erase(l);
    }
    int rt = *st.begin();
    dfs(rt);
    cout << max(dp[rt][0], dp[rt][1]);
    return 0;
}

恩。

生活愉快。