挺简单的，从 (n) 到 (1) 探讨是否能被加入。要加入的话必定是加入一条链，倍增以下看看要加多少，能不能加就可以了。
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
int n, k, hea[1000005], cnt, uu, vv, dep[1000005], fa[1000005][21];
bool vis[1000005];
struct Edge{
int too, nxt;
}edge[2000005];
void add_edge(int fro, int too){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
hea[fro] = cnt;
}
void dfs(int x, int f, int d){
dep[x] = d;
fa[x][0] = f;
for(int i=1; i<=20; i++)
fa[x][i] = fa[fa[x][i-1]][i-1];
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(t!=f)
dfs(t, x, d+1);
}
}
int f(int x){
int t=dep[x];
for(int i=20; i>=0; i--)
if(!vis[fa[x][i]])
x = fa[x][i];
return t-dep[x]+1;
}
int main(){
cin>>n>>k;
k = n - k - 1;
for(int i=1; i<n; i++){
scanf("%d %d", &uu, &vv);
add_edge(uu, vv);
add_edge(vv, uu);
}
dfs(n, 0, 1);
vis[0] = vis[n] = true;
for(int i=n-1; i && k; i--){
if(vis[i]) continue;
int tmp=f(i);
if(tmp<=k){
k -= tmp;
for(int j=i; !vis[j]; j=fa[j][0])
vis[j] = true;
}
}
for(int i=1; i<=n; i++)
if(!vis[i])
printf("%d ", i);
return 0;
}