树形 DP

[Ir1d]

https://oi-wiki.org/dp/tree/

[yanjinbin]

状态转移方程式 看得懂 代码 不想看 ,GG

[14w10]

状态转移方程看懂了，代码没看懂qwq

[zmxqs]

一般来说，树形dp都会以记忆化搜索的形式给出……

[JiananYuan]

贴个容易看得懂的代码，思路是一样的：

#include <iostream>
#include <vector>
#include <algorithm>
#define N 6005
using namespace std;
int n;
bool visited[N];
vector<int> T[N];
int dp[N][2]; // 从结点i往下所获最大value
// dp[i][0]表示i不参加时子树的maxValue，dp[i][1]表示i参加时子树的maxValue


void dfs(int k) { // 给定结点k，求以k为root的最大收益
    if (visited[k]) return ;
    visited[k] = true;
    for (int i = 0; i < T[k].size(); ++i) {
        int v = T[k][i];
        dfs(v);
        dp[k][0] += max(dp[v][0],dp[v][1]);
        dp[k][1] += dp[v][0];
    }
}


int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> dp[i][1];
    }
    bool tmp[N] = {0};
    for (int i = 1; i <= n-1; ++i) {
        int l,k;
        cin >> l >> k;
        T[k].push_back(l);
        tmp[l] = 1; // 是孩子结点，标记为1
    }
    for (int i = 1; i <= n; ++i) {
        if (tmp[i] == 0) { // 寻找唯一的根节点，找到之后dfs
            dfs(i);
            cout << max(dp[i][0],dp[i][1]) << "\n";
            break;
        }
    }
    return 0;
}

[straberrywakaka]

太难了。。😫

[AC2656512631]

#include <bits/stdc++.h>
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;

int n;

void solve() {
	cin >> n;
	vector<vector<int>> g(n + 1);
	for (int i = 1; i <= n - 1; i ++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	// root = 1时各个点的深度、每个点的子节点的数量（包括自身）
	vector<int> deep(n + 1, -1), num(n + 1, 0);
	auto dfs1 = [&] (auto dfs1, int u) ->int {
		int total = 1;
		for (auto v : g[u]) {
			if (deep[v] == -1) {
				deep[v] = deep[u] + 1;
				total += dfs1(dfs1, v);
			}
		}
		num[u] = total;
		return total;
	};
	deep[1] = 1;
	num[1] = n;
	dfs1(dfs1, 1);
	
	// 计算以每个点为根节点时的所有节点深度之和
	vector <int> sum(n + 1, 0);
	for (int i = 1; i <= n; i ++) {
		sum[1] += deep[i];
	}
	auto dfs2 = [&] (auto dfs2, int u) ->void {
		for (auto v : g[u]) {
			if (sum[v] == 0) {
				sum[v] = sum[u] + (n - num[v]) - num[v];
				dfs2(dfs2, v);
			}
		}
	};
	dfs2(dfs2, 1);
	
	int sum_max = -1, idx = -1;
	for (int i = 1; i <= n; i ++) {
		if (sum[i] > sum_max) {
			sum_max = sum[i];
			idx = i;
		}
	}
	
	cout << "         ";
	cout << idx << "\n";
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
//	cin >> T; cin.get();
	while (T --) solve();
	return 0;
}

[gitbugfsj]

想不明白为什么建图的时候，要加正反两条边？两次dfs都是从根1向下遍历，完全用不上反边啊？？？

[gitbugfsj]

↑↑↑脑抽了，当我没说

[ych2862715221]

有没有非递归的树形DP的实现

[AC2656512631]

非递归的形式我还没有见过

[AC2656512631]

找到踢我一下qaq

[TMSharweek]

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
#include <queue>

#define MAXN 6005

using namespace std;

int edge[MAXN];
queue<int> q;
int rd[MAXN], dp[MAXN][5], r[MAXN], cd[MAXN];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> r[i];
	}
	for (int i = 1; i < n; i++) {
		int k, l;
		cin >> k >> l;
		edge[k] = l;
		rd[l]++;
		cd[k]++;
	}
	for (int i = 1; i <= n; i++) {
		if (rd[i] == 0) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int qwq = q.front();
		q.pop();
		dp[qwq][1] += r[qwq];
		dp[edge[qwq]][0] += max(dp[qwq][1], dp[qwq][0]);
		if (dp[qwq][0] >= 0) {
			dp[edge[qwq]][1] += dp[qwq][0];
		}
		rd[edge[qwq]]--;
		if (rd[edge[qwq]] == 0) {
			q.push(edge[qwq]);
		}
	}
	int mx = -2147483647;
	for (int i = 1; i <= n; i++) {
		mx = max(mx, dp[i][1]);
		mx = max(mx, dp[i][0]);
	}
	cout << mx;

	return 0;
}

[TMSharweek]

几百年前写的，丑了一点

[csus4uwu]

在文中关于没有上司的舞会的代码实现中，dfs过程没必要判断vis，树的dfs访问不会出现重复的情况。

贴一个我用邻接表存树的代码，可能方便大家理解一点。

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
using ll = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    
    int n;
    cin >> n;

    vector<int> r(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
    }

    vector g(n + 1, vector<int>());
    bitset<10000> vis(0);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[v].push_back(u);
        vis[u] = 1;
    }    

    vector dp(n + 1, vector<int>(2));

    for (int i = 1; i <= n; i++) {
        dp[i][1] = r[i];
    }

    function<void(int)> dfs = [&](int u) {
        vis[u] = true;
        for (auto v : g[u]) {
            dfs(v);
            dp[u][1] += dp[v][0];
            dp[u][0] += max(dp[v][0], dp[v][1]);
        }
    };

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i);
            cout << max(dp[i][0], dp[i][1]) << endl;
            break;
        }
    }

    return 0;
}