原文链接https://www.cnblogs.com/zhouzhendong/p/9074226.html

题意

　　$\rm Codeforces$ 真是个令人伤心的地方。

　　伤心的 $zzd$ 给你一个有 $n$ 个节点的树，编号为 $i$ 的节点权值为 $2^i$。

　　让你砍掉其中 $k$ 个节点，使得剩余的所有节点都连通，并最大化剩余节点的权值和。输出方案。

　　$n\leq 10^6$

题解

　　伤心的 $zzd$ 再一次来到了令人伤心的 $\rm Codeforces$，并开心的 $9$ 分钟敲完并 $AC$ 了此题，并再一次伤心地发现这是在 $vp$ 结束后的第 $4$ 分钟。

　　我们考虑选择一颗子树，使得剩余节点的权值和最大。

　　显然我们可以贪心编号从大到小选择，能选就选。

　　考虑当前选出的子树状态为 $S$，下一个决策为节点 $i$ ，那么，新增的节点数就是节点 $i$ 到 $S$ 的距离。

　　只要新增之后不超出限制就可以了。

　　这个东西可以预处理倍增表来快速搞定。

代码

#include 
     
      using namespace std;const int N=1000005;struct gragh{	int cnt,y[N*2],nxt[N*2],fst[N];	void clear(){		cnt=0;		memset(fst,0,sizeof fst);	}	void add(int a,int b){		y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;	}}g;int n,lim,depth[N],fa[N],anst[N][21];int vis[N],tot=0,ans[N];void dfs(int x,int pre){	fa[x]=anst[x][0]=pre;	depth[x]=depth[pre]+1;	for (int i=1;i<=20;i++)		anst[x][i]=anst[anst[x][i-1]][i-1];	for (int i=g.fst[x];i;i=g.nxt[i])		if (g.y[i]!=pre)			dfs(g.y[i],x);}int main(){	scanf("%d%d",&n,&lim);	lim=n-lim;	g.clear();	for (int i=1,a,b;i
      
       =1;i--){		if (vis[i])			continue;		int j=i;		for (int k=20;k>=0;k--)			if (!vis[anst[j][k]])				j=anst[j][k];		if (tot+depth[i]-depth[j]+1>lim)			continue;		tot+=depth[i]-depth[j]+1;		vis[j]=1;		for (int k=i;k!=j;k=fa[k])			vis[k]=1;	}	tot=0;	for (int i=1;i<=n;i++)		if (!vis[i])			ans[++tot]=i;	for (int i=1;i<=tot;i++)		printf("%d ",ans[i]);	return 0;}