洛谷 P2458 分析（别看）

科技起源

2026-07-07 19:02:38

发布于：河北

0阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：求一个最小值

1.2 题目背景、允许、禁止与限制

背景：有一个有 $n$ 个结点的树
允许：放置尽可能低的保安花费，在结点 $i$ 放置保安需要花费一定金额并且可以使所有与结点 $i$ 相连的结点被看守
禁止：
限制：最后要使整棵树的每条边点都会被看守

1.3 题目数据范围与猜测

$1 \le d,n \le 1500 \longrightarrow O(n^2)$

1.4 一句话概括题意

有一个树，在结点 $i$ 放置保安需要花费一定金额并且可以使所有与结点 $i$ 相连的结点被看守。最终求使整棵树的每个点都会被看守到的情况下需放置的最低保安花费

2 题目破题推导

注：以下七种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

2.3 以终为始、以始为终

2.4 数学

~~先看2.5部分~~
如何计算耗费最低的呢？
我们可以记录一个总价值，并且将差额也记录，最终选取最小的差额对总价值进行影响（代码中具体看）

2.5 分情况考虑

可以尝试让自己覆盖自己
可以尝试让儿子覆盖自己
那一个结点有多个儿子怎么办呢？一定是选择那个耗费最低的孩子，这时候就看到2.4部分
可以尝试让父亲覆盖自己

2.6 手动推导

2.7 边界测试

3 模型匹配

提取关键词：
树+动态影响，是树形dp

4 具体方案

4.1 动态规划定义（重点）

首先，建立一个dp 数组
设置 ${dp_i}_0$ 代表用自己覆盖自己时的最小耗费
设置 ${dp_i}_1$ 代表用儿子覆盖自己时的最小耗费
设置 ${dp_i}_2$ 代表用父亲覆盖自己时的最小耗费

4.2 初始化

${dp_i}_0 \leftarrow a_i$
${dp_i}_1 \leftarrow 极大值$
${dp_i}_2 \leftarrow 0$

4.3 状态转移方程

其实 ${dp_i}_0$ 太好推了
${dp_i}_2$ 只有可能从上一项的 $j=0/1$ 转移过来，否则中间就会空出一个点（我自己不覆盖，孩子还得依靠我）
${dp_i}_1$ 本质上可以先正常记录所有孩子最小值，然后额外记录一个最小差额；如果发现所有孩子都不选择的是 ${dp_i}_0$ ，那就要让 ${dp_i}_0$ 差值最小的人强制变成 ${dp_i}_0$
这里可能不太清楚，可以看代码中的第二个注释应该就比较容易明白了

4.4 答案求取

不用说也知道

5 最终代码（禁止抄袭，仅用于参考）

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

int n;
const int N = 1555 + 10;
const int INF = 1e9 + 10;
int a[N];
int dp[N][3];// dp[i][]代表以i为根的子树中...，dp[i][0]代表自己控制自己，dp[i][1]代表让儿子控制，dp[i][2]代表假设让父亲控制
vector<int> g[N];
bool has_father[N];
int root;
void dfs(int u, int fa){
	dp[u][0] = a[u];
	dp[u][1] = INF;
	dp[u][2] = 0;
	bool ts = false;
	int gz_mn = INF;
	int sum_min = 0;
	for (int now : g[u]){
		if (now == fa){
			continue;
		}
		dfs(now, u);
		dp[u][0] += min({dp[now][0], dp[now][1], dp[now][2]});
		dp[u][2] += min(dp[now][0], dp[now][1]);
		sum_min += min(dp[now][0], dp[now][1]);
		gz_mn = min(gz_mn, dp[now][0] - min(dp[now][1], dp[now][0]));// 如果我强行让这个儿子改成站岗，需要多花多少钱;如果这个儿子本来就要站岗，多花的钱就是0，正好不需要多花费，如果全靠孙子呢？我就要找到那个改为站岗花费最小的，最后加上多改花的钱 
    }
    if (gz_mn != INF){
    	dp[u][1] = sum_min + gz_mn;
	}
}

int main(){
	
	cin >> n;
	for (int i = 1;i <= n;i++){
		int id;
		cin >> id;
		cin >> a[id];// cin >> k;
		int m;
		cin >> m;
		for (int j = 1;j <= m;j++){
			int r;
			cin >> r;
			g[id].push_back(r);
			g[r].push_back(id);
			has_father[r] = true;
		} 
	}
	for (int i = 1;i <= n;i++){
		if (has_father[i] == false){
			root = i;
			break;
		}
	}
	dfs(root, -1);
	cout << min(dp[root][0], dp[root][1]);
	
	return 0;
}