自动搬运

查看原文

来自洛谷，原作者为

	MingDynasty 最后在线时间:2025.8.23 21:03|team/76415出题组|开局一个碗,结局一根绳|坐标你猜|小升初蒟蒻,欢迎吊打|5天内2小号互关(大号paste/lb3d6tr9),可提醒,不可炸铃接龙|题解不懂私|主页article/hu9a8skr

搬运于2025-08-24 21:18:35，当前版本为作者最后更新于2025-05-21 12:19:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言：

皇帝又来写题解了。

题目传送门

看到树形二字，我们会想到树形 dp。

题目思路：

状态设置：

设 $dp[i][0/1]$ 表示当前的 $i$ 号节点是否装监控。

转移方程：

在转移过程中枚举儿子，先递归下去就行。回溯上来看当前节点装不装监控，如果装，那么儿子可以装也可以不装；如果不装，那么儿子就必须装。初始时输入每个节点装监控的代价即可。

设当前节点是 $x$，$x$ 的儿子是 $y$，01 表示装不装监控。以下就是方程转移式。

for(int i=0;i<e[x].size();i++){
  int y=e[x][i];
  dfs(y,x);   //先向下递归
  dp[x][0]+=dp[y][1];
  dp[x][1]+=min(dp[y][0],dp[y][1]);   //转移方程
}

注意：邻接表存图。

Code：

/*
    Auther:MingDynasty
    Problem:https://www.luogu.com.cn/problem/B4311
*/
#include<bits/stdc++.h>
using namespace std;
int n,a[323232],dp[323232][2];
vector<int> e[323232];
inline void dfs(int x,int fa){
	for(int i=0;i<(int)e[x].size();i++){
		if(e[x][i]==fa) continue;
		dfs(e[x][i],x);
		dp[x][0]+=dp[e[x][i]][1];
		dp[x][1]+=min(dp[e[x][i]][0],dp[e[x][i]][1]);   //方程转移式
	}
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>dp[i][1];
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,-1);
	cout<<min(dp[1][1],dp[1][0]);
	return 0;
}

祝各位通过本题！