[SHOI 2015] 聚变反应炉（树形背包 + 树形 DP） | 错题本

题目

[SHOI 2015] 聚变反应炉

分析

对于树上一个点操作后对相邻节点产生影响的题目，DP 状态的定义需要考虑父节点的影响。

定义 DP 状态 $dp[u][0/1]$ 表示 $u$ 的父亲节点 不给 $u$ 传输能量 $/$ 给 $u$ 传输能量 时激发 $u$ 的子树（包括 $u$）的最少代价。这样定义状态能知道父亲给自己传输的能量，再枚举子节点传输给自己的能量就可以转移了，然后涉及到“使子节点传输给自己的能量达到某一状态值的最小代价”，这是一个简单的树形背包问题。

代码

#include <bits/stdc++.h>

int Read() {
	int x = 0; char c = getchar();
	while (c < '0' || c > '9')
		c = getchar();
	while (c >= '0' && c <= '9')
		x = x * 10 + (c ^ 48), c = getchar();
	return x;
}

const int MAXN = 100000;
const int MAXP = 2000;
const int MAXW = 5;
const int INF = 0x3f3f3f3f;

int N;
int D[MAXN + 5], C[MAXN + 5];
int Dp[MAXP + 5][2], Bag[2][MAXW * MAXP + 5];
std::vector<int> G[MAXN + 5];

void Dfs(const int &u, const int &f) {
	int tot = 0;
	for (int v: G[u]) {
		if (v != f) {
			Dfs(v, u);
			tot += C[v];
		}
	}
	memset(Bag, 0x3f, sizeof Bag);
	Bag[0][0] = 0;
	int cur = 0, lst = 1;
	for (int v: G[u]) {
		if (v != f) {
			cur ^= 1, lst ^= 1;
			memset(Bag[cur], 0x3f, sizeof Bag[cur]);
			for (int i = 0; i <= tot - C[v]; i++) {
				Bag[cur][i + C[v]] = std::min(Bag[cur][i + C[v]], Bag[lst][i] + Dp[v][0]);
				Bag[cur][i] = std::min(Bag[cur][i], Bag[lst][i] + Dp[v][1]);
			}
		}
	}
	Dp[u][0] = Dp[u][1] = INF;
	for (int i = 0; i <= tot; i++) {
		Dp[u][0] = std::min(Dp[u][0], std::max(Bag[cur][i], Bag[cur][i] + std::max(D[u]- i, 0)));
		Dp[u][1] = std::min(Dp[u][1], std::max(Bag[cur][i], Bag[cur][i] + std::max(D[u] - C[f] - i, 0)));
	}
}

int main() {
	N = Read();
	int mxc = 0;
	for (int i = 1; i <= N; i++)
		D[i] = Read();
	for (int i = 1; i <= N; i++)
		mxc = std::max(mxc, C[i] = Read());
	for (int i = 1; i < N; i++) {
		int u = Read(), v = Read();
		G[u].push_back(v);
		G[v].push_back(u);
	}
	if (mxc <= 1) {
		int Ans = 0;
		for (int i = 1; i <= N; i++) {
			if (C[i] == 1) {
				Ans += D[i], D[i] = 0;
				for (int v: G[i])
					D[v]--;
			}
		}
		for (int i = 1; i <= N; i++)
			Ans += std::max(D[i], 0);
		printf("%d", Ans);
		return 0;
	}
	Dfs(1, 0);
	printf("%d", Dp[1][0]);
	return 0;
}

本文地址：https://blog.csdn.net/C20190102/article/details/110160305