Codeforces Round #480 (Div. 2) E. The Number Games(倍增+贪心)
程序员文章站
2022-04-11 10:23:40
...
题目链接
题意:给定一棵树,要求你删除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);
}