自动搬运

查看原文

来自洛谷，原作者为

	Accoty_AM 奋力一搏

搬运于2025-08-24 21:54:24，当前版本为作者最后更新于2019-08-11 15:26:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

大佬们是不是想难了。。这道题是考试20分钟打的，当时我还想，是不是想简单了

做这道题后建议做这道 P3523 [POI2011]DYN-Dynamite

贪心做法

我们每个节点记录两个值，f[x][0] 表示x到最近控制驿站的距离，f[x][1]表示x到最远没被控制点的距离

当f[x][0]+f[x][1]<=k时说明这个点能被控制，不能对上面的点贡献

当f[x][1]=k时，点x必须被控制，把f[x][0]改成0,f[x][1]改成-1,++ans,因为这时已经到达能控制点的最远距离，如果再向上，x就无法被控制，树上两点间的路径是唯一的

特判根节点是否能被控制，不能则++ans;

细节：稍微模拟可知统计答案时，f[x][0]和f[x][1]只有一个有用，当f[x][0]不能控制f[X][1]时，f[x][0]就失去作用了

贪心思路证明：

考虑被控制节点x，如果x可以向上移动一，并且仍然能控制x移动前能控制的点，就把x向上移动，显然，这样做是不会使答案变差的。

我们不知道x向上移动后能控制多少点，但显然，x有可能控制更多的点，这时把x移动到不能移动为止，x就成为了最优答案。

code 150ms 开O(2)变慢了，不造为啥

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cmath>
using namespace std;
namespace OI{
	#define rg register
	template<class T>
	inline void read(T &x){
		x=0;
		static char ch;
		static int f;
		ch=getchar();
		f=0;
		while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
		while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		x=f?-x:x;
	}
	const int N=200010;
	int head[N],nxt[N<<1],ver[N<<1],tot;
	int n,k,t,ans;
	//0 最近被控制点
	//1 最远没控制点
	int f[N][2];
	inline void add(int x,int y){
		ver[++tot]=y;
		nxt[tot]=head[x];
		head[x]=tot;
	}
	const int inf=0x3f3f3f3f;
	void dfs(int x,int fa){
		f[x][0]=inf;//初始
		f[x][1]=0;
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i];
			if(y==fa) continue;
			dfs(y,x);
			if(~f[y][1]) f[x][1]=max(f[x][1],f[y][1]+1);//这里如果下面的点被控制，就不考虑（因为如过继续考虑会多算贡献）
			f[x][0]=min(f[x][0],f[y][0]+1);
		}
		if(f[x][1]==k){//加控制点
			++ans;
			f[x][0]=0;
			f[x][1]=-1;
		}
		if(f[x][1]+f[x][0]<=k) f[x][1]=-1;//被控制标记
	}
	void main(){
		read(n),read(k),read(t);
		for(int x,y,i=1;i<n;++i){
			read(x),read(y);
			add(x,y);
			add(y,x);
		}
		dfs(1,0);
		if(~f[1][1]) ++ans;//特判根节点
		cout<<ans<<endl;
	}
}
int main(){OI::main();return 0;}	

希望能过QAQ