CF980E The Number Games

题目链接

题意分析

对于这道题 能留下大的尽量留下大的

我们以n为根 根是必选的

然后从大到小 如果当前点i未被留下 并且留下i到根n的所有点不会超过n-k 那么就全部留下

对于判断的话 由于一个点i被留下 那么i的祖先节点也会被留下

所以对于未被留下的点 我们使用倍增确定i往上最近的未被留下的点 复杂度O(nlogn)

然后暴力染色 由于每一个点只会被染色一次 所以复杂度是O(n)

CODE:

#include<bits/stdc++.h>
#define M 2008611
#define INF 200080
using namespace std;
int n,k,tot,cnt;
int to[M],nex[M],head[M];
int dep[M],fa[M][22];
bool tag[M];
void add(int x,int y)
{to[++tot]=y;nex[tot]=head[x];head[x]=tot;}
void dfs(int now,int fat)
{
	dep[now]=dep[fat]+1;fa[now][0]=fat;
	for(int i=1;(1<<i)<=dep[now];++i)
	fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=head[now];i;i=nex[i])
	{
		int v=to[i];
		if(v==fat) continue;
		dfs(v,now);
	}
}
int query(int now)
{
	int tmp=now;
//	printf("now is fro %d\n",now);
	for(int i=20;i>=0;--i)
	{
		if((1<<i)>dep[tmp]) continue;
		if(fa[tmp][i]&&!tag[fa[tmp][i]]) tmp=fa[tmp][i];
	}
//	printf("now is to %d\n",tmp);
	return dep[now]-dep[tmp]+1;
}
void update(int now)
{
	while(tag[now]==0)
	{
		tag[now]=1;++cnt;
		now=fa[now][0];
	}
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1,x,y;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(n,0);
	cnt=1;tag[n]=1;
	for(int i=n-1;i;--i)
	{
		if(tag[i]) continue;
		int tmp=query(i);
//		printf("now is %d %d\n",tmp,cnt);
		if(tmp+cnt<=n-k) update(i);
		if(n-k==cnt) break;
	}
	for(int i=1;i<=n;++i) if(!tag[i]) printf("%d ",i);
	return 0;
}