洛谷 P2458 分析（别看）

科技起源的小号1

2026-10-18 12:14:00

发布于：天津

6阅读

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 第二步：数学（如何选择耗费最低的孩子）

我们可以记录一个总价值，并且将差额也记录，最终选取最小的差额对总价值进行影响（代码中具体看）

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$
这里可能不太清楚，可以看代码中的第二个注释应该就比较容易明白了

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;
}