欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #480 (Div. 2) E. The Number Games(倍增+贪心)

程序员文章站 2022-04-11 10:23:40
...

题目链接
Codeforces Round #480 (Div. 2) E. The Number Games(倍增+贪心)
Codeforces Round #480 (Div. 2) E. The Number Games(倍增+贪心)
题意:给定一棵树,要求你删除k个点,删除点后整个数的依然连通,同时剩下点的点权要最大。
思路:以n为根,贪心的选择尽量大的点,然后要判断这个点能不能选,能选的话,把它到根节点路径上的点也肯定要一起选,check函数就是用来判断i点能不能选(能不能选的关键是看,i到它的祖先节点中第一个没有被选的点的点数目是否小于等于k),LCA倍增加速。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+1;
vector<int>g[maxn];
int parent[maxn][21],vis[maxn];
void dfs(int x,int fa)
{
	parent[x][0]=fa;
	for(int i=1;i<=20;++i) parent[x][i]=parent[parent[x][i-1]][i-1];
	for(int to:g[x])
	{
		if(to==fa) continue;
		dfs(to,x);
	}
}
bool check(int x,int cnt)
{
	for(int j=20;j>=0;--j)
	{
		if(vis[parent[x][j]]==0)
		{
			cnt-=(1<<j);
			x=parent[x][j];
		}
	}
	return cnt>=1;
}
int main()
{
	int n,k,u,v;
	scanf("%d %d",&n,&k);
	for(int i=1;i<n;++i)
	{
		scanf("%d %d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=0;i<=20;++i) parent[n][i]=n;
	dfs(n,n);
	k=n-1-k;
	vis[n]=1;
	for(int i=n-1;i>=1;--i)
	if(check(i,k))
	{
		int x=i;
		while(vis[x]==0) vis[x]=1,x=parent[x][0],k--;
	}
	for(int i=1;i<=n;++i) if(vis[i]==0) printf("%d ",i);
}
相关标签: LCA