P2515-软件安装-树形DP-题解

发表于 2023-08-16 分类于信奥，题解阅读次数：

原题链接：Link

思路分析

树形 DP 打多了就容易不看题，这个题并没有要求依赖关系形成一棵树，而是可能出现循环依赖。

所以要先用 tarjan 缩点，之后再把所有连通块的根连接到超级源点。（注意顺序！！！一个环是没有根的，所以要先缩点再连超级源）

之后是普通的树上背包：定义 \(f_{u,k}\) 表示以 \(u\) 为根的子树最大代价为 \(k\) 能够获得的最大价值。处理的过程中，如果当前处理到儿子 \(v\)，则 \(f_{u,k}=\max_{j=c_{u}}^{k}{(f_{u,j}+f_{v,k-j})}\)。感性理解一下，就是考虑多少代价分配给 \(v\)，剩下的代价分配给 \(u\) 和那些已经处理过的儿子。

AC 代码

code

#include <bits/stdc++.h>
using namespace std;
#define FILE_IO
namespace io {...};
using namespace io;
const int maxn = 1e2 + 5, maxm = 5e2 + 5;

vector<int> son[maxn], sson[maxn];
int n, m;
int a[maxn], c[maxn], aa[maxn], cc[maxn], bel[maxn], cnt;
int dp[maxn][maxm];

void dfs(int u) {
	for (int i = 0; i < cc[u]; i++) dp[u][i] = -9999999;
	for (int i = cc[u]; i <= m; i++) dp[u][i] = aa[u];
	for (auto v : sson[u]) {
        // write(v);
		dfs(v);
		for (int i = m; i >= cc[u] + cc[v]; i--) {
			for (int j = cc[v]; j + cc[u] <= i; j++) {
				dp[u][i] = max(dp[u][i], dp[u][i - j] + dp[v][j]);
			}
		}
	}
}

stack<int> st;
bool in_st[maxn];
int dfn_cnt, dfn[maxn], low[maxn];

void tarjan(int u) {
    dfn[u] = low[u] = ++dfn_cnt;
    st.emplace(u);
    in_st[u] = true;
    for (auto v : son[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (in_st[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        int v; ++cnt;
        do {
            v = st.top();
            st.pop();
            in_st[v] = false;
            bel[v] = cnt;
        } while (v != u);
    }
}

bool book[maxn];

int main() {
	read(n); read(m);
    for (int i = 1; i <= n; i++) {
        read(c[i]);
    }
    for (int i = 1; i <= n; i++) {
        read(a[i]);
    }
	for (int i = 1; i <= n; i++) {
		int s;
		read(s);
		if (s) son[s].emplace_back(i);
	}
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        aa[bel[i]] += a[i];
        cc[bel[i]] += c[i];
        for (int x : son[i]) {
            if (bel[i] != bel[x]) {
                sson[bel[i]].emplace_back(bel[x]);
                book[bel[x]] = true;
            }
        }
    }
    for (int i = 1; i <= cnt; i++) if (!book[i]) sson[0].emplace_back(i);
	dfs(0);
	write(dp[0][m]);
	return 0;
}