CF980E

题面

Panel 国将举办名为数字游戏的年度表演。每个省派出一名选手。

国家有 n 个编号从 1 到 n 的省，每个省刚好有一条路径将其与其他省相连。第 i 个省出来的代表有 2^i 名粉丝。

今年，主席打算削减开支，他想要踢掉 k 个选手。但是，被踢掉的选手的省将很 angry 并且不会让别的任何人从这个省经过。

主席想确保所有剩下选手的省都互相可达，他也希望最大化参与表演的选手的粉丝数。

主席该踢掉哪些选手呢？

升序输出要踢掉的选手编号。

因为是二进制表示权值，可知越大的数越要保留，因为所有比它小的数的和都比他要小

因此要贪心从n-1~1枚举是否可以保留（当然是以n为根的树，n号节点一定要保留）

#include <cstdio>

#include <vector>

#include <cctype>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 1000005

inline int read()

{

  int s=,f=; char ch;ch=getchar();

  while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}

  while(isdigit(ch)){s=s*+(ch-'');ch=getchar();}

  return f?-s:s;

}

int n,m,k,in1[N],cnt=,fa[N][];

bool bo[N];

vector<int>G[N];

inline void dfs(int x,int pre)

{

  fa[x][]=pre; int i; for(i=;i<=;i++)fa[x][i]=fa[fa[x][i-]][i-];

  for(i=;i<(int)G[x].size();i++)if(G[x][i]!=pre)dfs(G[x][i],x);

}

inline int get(int x)

{

  int i,re=;

  for(i=;~i;i--)

  {

    if(!bo[fa[x][i]]){x=fa[x][i];re+=(<<i);}

  }return re+;

}

#define r(n) n=read()

int main()

{

    int i,x,y,j=; r(n);r(m);

    for(i=;i<n;i++)

  {

    r(x);r(y);G[x].push_back(y);G[y].push_back(x);

  }dfs(n,n); memset(bo,,sizeof bo);bo[n]=; k=n--m;

  for(i=n-;i>=;i--)

  {

    if(bo[i])continue; int le=get(i),f;

    if(le<=k)

    {

      f=i;k-=le;for(j=;j<=le;j++){bo[f]=;f=fa[f][];}

    }

  }

  j=;for(i=;i<=n&&j<m;i++)if(!bo[i])printf("%d ",i),j++;printf("\n");

}