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
| #include <bits/stdc++.h>
using namespace std; #define all(a) (a).begin(),(a).end() #define pb(x) push_back(x) #define CLR(arr,val) memset(arr,val,sizeof(arr)) #define FAST_IO ios::sync_with_stdio(false);cin.tie(0); #define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q) const int N = 1e6 + 7; struct edge { int to, nxt; edge() {} edge(int _to, int _nxt): to(_to), nxt(_nxt) {} } E[N << 1]; int head[N], tot; int dep[N], vis[N], fa[N][21];
void init() { CLR(head, -1); tot = 0; } void add(int s, int t) { E[tot] = edge(t, head[s]); head[s] = tot++; } void dfs(int u, int f, int d) { fa[u][0] = f; dep[u] = d; for (int i = head[u]; ~i; i = E[i].nxt) { int v = E[i].to; if (v != f) dfs(v, u, d + 1); } } void del(int x) { if (vis[x] || !x) return ; vis[x] = 1; del(fa[x][0]); } int main(void) { int n, k, i, a, b, j; init(); scanf("%d%d", &n, &k); for (i = 1; i < n; ++i) { scanf("%d%d", &a, &b); add(a, b); add(b, a); } dfs(n, 0, 0); for (j = 1; j <= 20; ++j) { for (i = 1; i <= n; ++i) fa[i][j] = fa[fa[i][j - 1]][j - 1]; } int res = n - k - 1; vector<int>v; vis[n] = 1; for (i = n - 1; i >= 1 && res > 0; --i) { if (vis[i]) continue; int x = i; for (j = 20; j >= 0; --j) { if (fa[x][j] && !vis[fa[x][j]]) x = fa[x][j]; } x = fa[x][0]; int kpcnt = dep[i] - dep[x]; if (res < kpcnt) continue; del(i); res -= kpcnt; } for (i = 1; i <= n; ++i) if (!vis[i]) printf("%d ", i); puts(""); return 0; }
|