自动搬运

查看原文

来自洛谷，原作者为

	new2zy 你强任你强，我绝不示弱！

搬运于2025-08-24 21:37:55，当前版本为作者最后更新于2018-08-30 16:46:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题解 P2458 [SDOI2006]保安站岗

题目传送门：

https://www.luogu.org/problemnew/show/P2458

PS：这题真心不错，也算是一道经典的树形DP了

=================================================

题目大意：

在一棵点有点权的树上，选择一些点，这些点能将所有与它们相连的点覆盖，最终将整棵树上的点全部覆盖，试求最小代价

算法分析：

emmm。。。看完题目，一眼就看出是个树形DP

（别问我怎么看出来的）（逃

我们发现，要使所有点最终全部被覆盖，那么无非有3种状态：

（以下全部都是对于要覆盖任意一个以x为根的子树来说的）
（其中我们设y节点为y的儿子，fa为x的父亲）
1.x节点被自己覆盖，即选择x点来覆盖x点

2.x节点被儿子y覆盖，即选择y点来覆盖x点

3.x节点被父亲fa覆盖，即选择fa点来覆盖x点

借此三种状态，我们可以设f[x][0/1/2]为让以x为根的子树中的节点全部被覆盖，且x点的被覆盖情况为1/2/3时的最小代价

为了方便，我们不妨设这三种情况分别为：

1.f[x][0]---对应上面的1

2.f[x][1]---对应上面的2

3.f[x][2]---对应上面的3

既然是DP，总是有转移方程的，我们想一下dp方程要如何设计

设计状态转移方程：

(1):对应上面的1.

f[x][0]=∑ min(f[y][0],f[y][1],f[y][2]) + val[x]

其中val[x]是选择x点的代价

我们很容易想到，在节点x被选择之后，我们就可以无拘无束了（蛤?），也就是说对于x儿子节点y的状态可以不去考虑，因为x节点被选择之后y节点无论如何也会被覆盖到，所以我们在儿子y的所有状态里取min，累加起来就行了

(2):对应上面的3（先讲3，因为2比较难以理解，放到了后面）

f[x][2]=∑ min(f[y][0],f[y][1])

为什么3情况对应的转移方程要这样写呢?

我们不妨这样理解，对于x节点我们让它的父亲节点fa覆盖它，那么根据我们的状态设计，此时必须要满足以x的儿子y为根的子树之中所有点已经被覆盖

那么这时就转化为一个子问题，要让y子树满足条件，只有两种决策：要么y被y的儿子覆盖，要么被y自己覆盖（即选择y节点），只需要在y的这两种状态取min累加就可以了

(3):对应上面的2（DuangDuangDuang 敲黑板划重点啦）

f[x][1]=∑ min(f[y][0],f[y][1])，如果选择的全部都是f[y][1],要再加上min(f[y][0]-f[y][1])

这又是什么意思呢？真是让人摸不着头发，，，质壁分离（逃

到了这里，我们就要回顾一下我们设计的dp状态了：

** 设f[x][0/1/2]为让以x为根的子树中的节点全部被覆盖，且x点的被覆盖情况为1/2/3时的最小代价**

先提示一下，如果你理解了下面，那么本题是很简单的。。如果你没理解，就返回到这里再看一遍吧，我就在这里等着你

咳咳。。说正经的。。（逃

对于此时的状态，f[x][1]代表对于节点x让x被自己的儿子覆盖，那么和分析（2）一样，都要先满足此时以y的子树已经满足了条件，才能进行转移，这就是前面那部分：∑ min(f[y][0],f[y][1])的来历，那么后面那一长串又是怎么回事呢?

我们可以这样理解，此时既然要保证x点是被自己的儿子覆盖的，那么如果此时y子树已经满足了全部被覆盖，但是y此时被覆盖的状态却是通过y节点自己的儿子达到的，那么x就没有被儿子y覆盖到，那么我们不妨推广一下，如果x所有的儿子y所做的决策都不是通过选择y点来满足条件，那么我们就必须要选择x的一个子节点y，其中y满足f[y][0]-f[y][1]最小，并把这个最小的差值累加到f[x][1]中去，这样才能使得x点被自己的儿子覆盖，状态f[x][1]也才能合理地得到转移

好了，如果你还是没有太懂这个（3）的设计过程，请你回到之前再仔细看几遍

如果你已经理解了上面，那么恭喜你这个题，你已经A掉了

因为转移方程既然有了，那么我们就只需要最后的答案了

由于题目中没有说这棵树的根节点是哪个，所以你可以默认1就是根，或者开一个数组在加边的时候记录一下每个点的入度，最后没有入度的点就是根（但好像没有区别，毕竟我A掉了）

最后答案即为min(f[root][0],f[root][1])

因为根节点没有父亲,所以不需要考虑它的f[root][2]状态

那这样的花。。下面就放一下我丑陋的代码好了（逃

还请dalao们不喜勿喷

PS：代码里也有解释，希望能帮到你更深地理解一下本题

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int inf=1e9+7;
inline int read()
{
    int p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return f*p;}
const int maxn=1503;
struct Edge
{
	int from,to;
}p[maxn<<1];
int n,cnt,head[maxn<<1],val[maxn];
int f[maxn][4];
//设状态f[x][0],f[x][1],f[x][2]分别表示
//对于x点,被自己覆盖,被自己的儿子覆盖,被自己的父亲覆盖时
//满足以x为根的子树所有点都被覆盖的最小代价 
inline void add_edge(int x,int y)//加边 
{
	cnt++;
	p[cnt].from=head[x];
	head[x]=cnt;
	p[cnt].to=y;
}
inline void TreeDP(int x,int fa)//树形DP 
{
	f[x][0]=val[x];//初值:选择x点 
	int sum=0,must_need_mincost=inf;
	for(int i=head[x];i;i=p[i].from)
		{
			int y=p[i].to;
			if(y==fa)continue;
			TreeDP(y,x);
			int t=min(f[y][0],f[y][1]);
			f[x][0]+=min(t,f[y][2]);
            //自己被自己覆盖:儿子怎么样都行 
			f[x][2]+=t;
            //自己被父节点覆盖:儿子必须合法,要么选择儿子,要么是儿子被儿子的儿子覆盖 
			//以下是对f[x][1]的转移，请好好理解 
			if(f[y][0]<f[y][1])sum++;
            //如果选择儿子节点更优,选上,计数器sum++，证明选过f[y][0] 
			else must_need_mincost=min(must_need_mincost,f[y][0]-f[y][1]);
			//否则记录一个最小的必须支付代价
            //因为最后要保证x点被y覆盖,必须要找差值最小的,这样才最优 
			f[x][1]+=t;//自己被儿子覆盖,那么儿子必须合法 
		}
	if(!sum)f[x][1]+=must_need_mincost;
	//对于f[x][1]转移:如果一个f[y][0]都没选过,那么必须从差值最小的儿子里面选择一个 
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		{
			int x=read();
			val[x]=read();
			int num=read();
			while(num>0)
				{
					int y=read();
					add_edge(x,y);
					add_edge(y,x);
					num--;
				}
		}
	TreeDP(1,0);
	printf("%d",min(f[1][0],f[1][1]));
	//由于根节点没有父节点,最后答案就是min(f[1][0],f[1][1])
	//即1节点被自己覆盖或者被自己的儿子覆盖 
	return 0;
}

好了，到这里就没了。。。

如果有什么不懂的还可以私信我，或者在评论区里留言也行

欢迎各位奆佬指出错误，我会改正的

最后推广一下自己的blog：

https://www.luogu.org/blog/new2zy/

感谢阅读，拜拜~~~ >=<