传送门

题面

题目描述

给定n个点的树，编号$1~n$，每个节点上有权值，编号为i的节点权值为$2^i$。BSNY想去掉k个点，并且希望剩下的点两两相互连通的，也就是剩下$(n-k)$个点为原先树的子树。在此基础上，BSNY想让剩下的子树权值和最大，请你编程告诉他，应该去掉哪$k$个点。
例如$n=6, k=3$，树的边为：

2 1 
2 6 
4 2 
5 6 
2 3

去掉1 3 4三个点，剩下的2 5 6三个点仍然构成树，并且权值和最大为：$2^2+2^5+2^6$。

输入

第一行输入$n, k$
接下来$n-1$行，输入$n-1$条无向边，构成树

输出

从小到大输出去掉的k个点的编号

样例输入

8 4
2 6
2 7
7 8
1 2
3 1
2 4
7 5

样例输出

1 3 4 5

提示

30%的数据$1<=k<n<=100$
50%的数据$1<=k<n<=1000$
另有10%的数据 树退化成链
100%的数据$1<=k<n<=10^6$

题解

想不明白为什么不能直接贪心
首先可以发现n是必选的，然后尝试选n-1…此时需要计算出想要选中的点向上到多上才能遇到第一个已选中的点，可以倍增实现
然后标记暴力打就行了，因为最多所有点都打一个标记

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node{
    int Next,y;
}Pth[2000005];
int head[1000005],cnt;
void add(int x,int y){
    cnt++;
    Pth[cnt]={head[x],y};
    head[x]=cnt;
}

int n,k,t;
int fa[1000005][20],d[1000005];
bool checked[1000005];

void bfs(){
    queue <int> q;
    q.push(n); d[n]=1;
    while (!q.empty()){
        int x=q.front(); q.pop();
        for (int i=head[x];i;i=Pth[i].Next){
            int y=Pth[i].y;
            if (d[y]) continue;
            d[y]=d[x]+1;
            fa[y][0]=x;
            for (int j=1;j<=t;++j){
                fa[y][j]=fa[fa[y][j-1]][j-1];
            }
            q.push(y);
        }
    } 
}

int calc(int p){
    if (checked[p]) return 0;
    int rp=p;
    for (int i=t;i>=0;--i){
        if (fa[p][i] && !checked[fa[p][i]]){
            p=fa[p][i];
        }
    }
    return d[rp]-d[p]+1;
}
void tag(int p){
    while (!checked[p]){
        k--; checked[p]=1;
        p=fa[p][0];
    }
}

int main(){
    cin>>n>>k;
    t=log(n)/log(2); k=n-k;
    for (int i=1;i<n;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    bfs();
    checked[n]=1;
    k--;
    for (int i=n-1;i>=1;--i){
        if (calc(i)<=k){
            tag(i);
        }
    }
    for (int i=1;i<=n;++i){
        if (!checked[i]) printf("%d ",i);
    }
    puts("");
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/%E6%9C%80%E5%A4%A7%E6%9D%83%E5%80%BC%E5%AD%90%E6%A0%91/