「Codeforces 980E」The Number Games

发表于 | | 阅读次数:
字数统计: 927 字

Description

题目链接：Codeforces 980E

Panel 国将举办名为数字游戏的年度表演。每个省派出一名选手。

国家有 $n$ 个编号从 $1$ 到 $n$ 的省，每个省刚好有一条路径将其与其他省相连。第 $i$ 个省出来的代表有 $2^i$ 名粉丝。

今年，主席打算削减开支，他想要踢掉 $k​$ 个选手。但是，被踢掉的选手的省将很生气，并且不会让别的任何人从这个省经过。

主席想确保所有剩下选手的省都互相可达，他也希望最大化参与表演的选手的粉丝数。

主席该踢掉哪些选手呢？

数据范围：$1\le k<n\le 10^6​$

Solution

显然这是一棵树，我们要踢掉的一定是当前度数为 $1$ 的点。换言之，保留的点一定是原树的一个连通块。

再观察 $2^i$ 的性质，我们发现保留一个点 $i$ 一定比保留所有的 $1,2,\dots,i-1$ 更优。那么肯定要尽量删除标号小的点。但是反例如下：

$n=5$，$k=3$，这是一条链：$4-1-5-2-3$

如果直接删除标号小的，那么删除的点为 $3,2,4$。而最优解为删除 $4,1,3​$。

这种贪心过程由于没法考虑到非叶子节点的大小，因此是错误的。那么我们考虑一个反面：尽量保留标号大的节点。为了方便操作，我们以 $n$ 作为根节点（因为它一定是要保留的）。具体操作过程如下：

  1. 从大到小遍历节点，假设当前节点为 $x$。我们把已经保留的点叫做标记点。
  2. 如果节点 $x$ 到根节点经过的标记点有 $m$ 个，那么如果要保留点 $x$，还需要额外保留它到根路径上的非标记点 $dep_x-m-1$ 个（其中 $dep$ 为深度，根的深度为 $1$），共需要保留 $dep_x-m$ 个。
  3. 如果 $dep_x-m$ 不大于当前允许保留的节点个数，那么把这些点全部保留；否则不操作。
  4. 跳到第 $1$ 步。

最后考虑实现问题：

  • 如何维护标记点个数？

    我们发现每加入一个标记点 $x$，$x$ 子树内的节点到根的标记点个数都会增加 $1$，直接求出 $\text{DFS}$ 序，用树状数组维护即可。

  • 如何把 $dep_x-m$ 个点设为标记点。

    暴力往上跳即可，跳到标记点就退出。每个点最多经过 $1$ 次，复杂度正确。

时间复杂度：$O(n\log n)$

Code

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
 
#include <cstdio>

const int N=1e6+5,M=2e6+5;
int n,k,tot,idx,lnk[N],ter[M],nxt[M],dfn[N],dep[N],fa[N],sz[N],b[N];
bool flg[N];

void add(int u,int v) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot;
}
void dfs(int u,int p) {
    dfn[u]=++idx,dep[u]=dep[fa[u]=p]+1,sz[u]=1;
    for(int i=lnk[u];i;i=nxt[i]) {
        int v=ter[i];
        if(v==p) continue;
        dfs(v,u);
        sz[u]+=sz[v];
    }
}
void modify(int x,int v) {
    for(;x<=n;x+=x&-x) b[x]+=v;
}
int query(int x) {
    int ans=0;
    for(;x;x^=x&-x) ans+=b[x];
    return ans;
}
int main() {
    scanf("%d%d",&n,&k);
    k=n-k;
    for(int i=1;i<n;++i) {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(n,0);
    flg[n]=1,--k;
    modify(dfn[n],1),modify(dfn[n]+sz[n],-1);
    for(int i=n-1;i>=1;--i) {
        if(!flg[i]&&dep[i]-query(dfn[i])<=k) {
            for(int x=i;x!=n&&!flg[x];x=fa[x]) {
                modify(dfn[x],1),modify(dfn[x]+sz[x],-1);
                flg[x]=1,--k;
            }
        }
    }
    for(int i=1;i<=n;++i) if(!flg[i]) printf("%d ",i);
    puts("");
    return 0;
}
0%