题意分析
给定一棵 $n$ 个节点的树，第 $i$ 个节点的权值为 $2^i$。从中删除 $k$ 个节点，使得剩下 $n-k$ 个节点联通且权值和最大。
求删除哪 $k$ 个节点。
贪心性质
权值为 $2^i$ 毫无疑问是极其特殊的，因此我们可以考虑有没有一些性质。
显然，$2^x>2^{x-1}+2^{x-2}+2^{x-3}+\cdots+2^{0}$，因此我们可以考虑贪心。
即：因为需要使权值和最大，因此让删除的 $k$ 个点的权值和尽可能小，所以让这 $k$ 个点的编号尽可能小。
增加点
删除点不好做。
因此我们可以尝试转换为增加点——若确定了剩下 $n-k$ 个点，也即确定了删除的 $k$ 个点。
那么我们就需要贪心地使增加的点的编号尽可能大，则 $n$ 号点肯定是需要保留的。
以 $n$ 为根节点建立一棵有根树，加入节点 $i$ 即将 $i$ 至 $n$ 的路径上所有的点加入。
贪心从大致小加入节点即可。
维护路径上尚未加入的点的数量
这样，我们才能判断当前节点 $i$ 能否加入（如果加入后有根树内的节点数大于 $n-k$ 则不符合条件）。
考虑暴力的思路，一个一个节点向上跳，跳到已经加入有根树的节点时停止，跳的过程中计数即可。
那么我们优化这样的思路，使用倍增 $\mathcal O(\log n)$ 向上跳，跳的同时计数即可。
AC 代码
时间复杂度：$\mathcal O(n\log n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e6;
struct graph{
struct edge{
int v,r;
}a[N-1<<1|1];
int size,h[N+1];
void create(int u,int v){
a[++size]={v,h[u]};
h[u]=size;
}
}g;
int n,k,f[N+1][__lg(N+1)+1];
bool flag[N+1];
void dfs(int x,int fx){
f[x][0]=fx;
for(int i=g.h[x];i;i=g.a[i].r){
int &v=g.a[i].v;
if(v==fx){
continue;
}
dfs(v,x);
}
}
void pre(){
dfs(n,0);
k--;
flag[n]=true;
for(int i=1;(1<<i)<=n;i++){
for(int x=1;x<=n;x++){
f[x][i]=f[f[x][i-1]][i-1];
}
}
}
int query(int x){
int ans=1;
for(int i=__lg(n);i>=0;i--){
if(!f[x][i]){
continue;
}
if(flag[f[x][i]]){
continue;
}
ans+=(1<<i);
x=f[x][i];
}
return ans;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>k;
k=n-k;//注意k此时表示有根树能加入的节点数
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g.create(u,v);g.create(v,u);
}
pre();
vector<int>ans;
for(int i=n-1;i>=1;i--){
if(flag[i]){
continue;
}
int pl=query(i);
if(pl<=k){
k-=pl;
int x=i;
while(!flag[x]){
flag[x]=true;
x=f[x][0];
}
}else{
ans.push_back(i);
}
}
for(int i=ans.size()-1;i>=0;i--){
cout<<ans[i]<<' ';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
