【CodeForces 980E】The Number Games / 题解

题目描述

Panel 国每年举办名为 Number Games的节目，全国每个区都将派出一名代表参赛。

该国有n个区，编号从1到n，每个区只有一条路径连接到其他区。每个区有一定数量的粉丝，来自$i$区的选手的粉丝数等于$2^i$。

今年，总统决定降低成本。他想从比赛中取消$k$个参赛者。然而，被取消比赛资格区域的民众因此将很愤怒，他们将不允许任何人穿过他们的区域。

总统希望确保所有剩下的参赛者都来自可以相互联系的地区。他还希望最大化参赛选手的粉丝总数。

总统应该删除哪些参赛者？

输入的第一行包含两个整数 $n$ and $k$ ($1 leq k < n leq 10^6$) — Panel 国的区域总数，以及总统希望取消的参赛者个数。 接下来 $n-1$ 行每行包含两个整数 $a$ 和 $b$ ($1 leq a, b leq n$, $a e b$), 描述连接两个不同区域 $a$ 和 $b$ 的双向道路。保证每两个区域间至多有一条路。

输出 $k$ 个由空格分隔开的整数: 以升序排列的所有应该被移除的区域编号。

我们发现点权是$2^i$，也就是说最大的点权比剩下的加起来都大。

所以我们要尽量保留编号大的点，直接贪心就可以了。

具体地，以$n$为根预处理倍增数组，直接保留点$n$，然后从大到小$O(n)$枚举每一个点，倍增找出它离保留的点的最近距离，暴力标记路径上的所有点。

代码

#include 
#define maxn 1000100
using namespace std;
struct Edge{
    int to,next;
    Edge(int a=0,int b=0){
        to=a,next=b;
    }
}l[maxn*2];
int head[maxn],cnt,n,k,p[maxn][21];
bool vis[maxn];
void Add(int a,int b){
    l[++cnt]=Edge(b,head[a]);
    head[a]=cnt;
}
void dfs(int u,int f){
    p[u][0]=f;
    for (int i=1;i<=20;i++)
        p[u][i]=p[p[u][i-1]][i-1];
    for (int i=head[u];i;i=l[i].next)
        if (l[i].to!=f) dfs(l[i].to,u);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k; int t1,t2;
    for (int i=1;i>t1>>t2;
        Add(t1,t2),Add(t2,t1);
    }
    dfs(n,0);int res=n-k-1;vis[n]=1;
    for (int v=n-1;v>=1;v--){
        int x=v,t=v,dis=0;
        if (vis[x]) continue;
        for (int i=20;i>=0;i--){
            if (!p[x][i]) continue;
            if (!vis[p[x][i]]) x=p[x][i],dis+=(1<res) continue;res-=dis;
        while(t!=x) vis[t]=1,t=p[t][0];
    }
    for (int i=1;i<=n;i++)
    if (!vis[i]) cout<