The Number Games

  • 贪心选择,树剖维护
  • 代码:

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define MAXN 1000010

int n, k;
int head[MAXN], to[MAXN << 1], next[MAXN << 1], tot = 0;
inline void $(int u, int v){
    next[tot] = head[u], to[tot] = v, head[u] = tot++;
    next[tot] = head[v], to[tot] = u, head[v] = tot++;
}
int size[MAXN], fa[MAXN], deep[MAXN], top[MAXN];
void dfs0(int x){
    size[x] = 1;
    for(int i = head[x];~i;i = next[i]){
        if(to[i] == fa[x])continue;
        fa[to[i]] = x;
        deep[to[i]] = deep[x] + 1;
        dfs0(to[i]);
        size[x] += size[to[i]];
    }
}
int dfn[MAXN], pos[MAXN], dfsclk = 0;
void dfs1(int x){
    pos[dfn[x] = ++dfsclk] = x;
    if(!~top[x])top[x] = x;
    int max = 0;
    for(int i = head[x];~i;i = next[i])if(to[i] != fa[x] && size[to[i]] > size[max])max = to[i];
    if(max)top[max] = top[x], dfs1(max);
    for(int i = head[x];~i;i = next[i])if(to[i] != fa[x] && to[i] != max)dfs1(to[i]);
}
int sum[MAXN << 2], tag[MAXN << 2];
inline int pushDown(int x, int l, int r){
    int mid = (l + r) >> 1;
    if(tag[x]){
        sum[x << 1] = mid - l + 1;
        sum[x << 1 | 1] = r - mid;
        tag[x << 1] = tag[x << 1 | 1] = 1;
        tag[x] = 0;
    }
    return mid;
}
int query(int n, int l, int r, int L, int R){
    if(l == L && r == R)return sum[n];
    int mid = pushDown(n, l, r);
    if(R <= mid)return query(n << 1, l, mid, L, R);
    if(L > mid)return query(n << 1 | 1, mid + 1, r, L, R);
    return query(n << 1, l, mid, L, mid) + query(n << 1 | 1, mid + 1, r, mid + 1, R);
}
void set(int n, int l, int r, int L, int R){
    if(l == L && r == R)return tag[n] = 1, sum[n] = (r - l + 1), void();
    int mid = pushDown(n, l, r);
    if(R <= mid)set(n << 1, l, mid, L, R);
    else if(L > mid)set(n << 1 | 1, mid + 1, r, L, R);
    else set(n << 1, l, mid, L, mid), set(n << 1 | 1, mid + 1, r, mid + 1, R);
    sum[n] = sum[n << 1] + sum[n << 1 | 1];
}
inline int count(int x){
    register int ret = 0;
    while(x){
        ret += query(1, 1, n, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    return ret;
}
inline int fill(int x){
    while(x){
        set(1, 1, n, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
}
int main(){
    memset(head, -1, sizeof(head));
    memset(top, -1, sizeof(top));
    std::ios::sync_with_stdio(0);
    std::cin >> n >> k;
    for(int i = 1;i < n;i++){
        int u, v; std::cin >> u >> v;
        $(u, v);
    }
    deep[n] = 1; dfs0(n); dfs1(n);
    k = n - k - 1;
    set(1, 1, n, dfn[n], dfn[n]);
    for(int i = n - 1;i;i--){
        int need = deep[i] - count(i);
        if(need > k)continue;
        k -= need;
        fill(i);
    }
    for(int i = 1;i <= n;i++)if(!query(1, 1, n, dfn[i], dfn[i]))printf("%d ", i);
    puts("");
    return 0;
}

Leave a Reply