CF1593E Gardener and Tree(拓扑)题解

发布于 2021-10-21  42 次阅读


题目大意

$T$ 组数据。

现在有一棵 $n$ 个结点的树,对其进行 $k$ 次操作,每次操作删除树的所有叶子结点。

现在问 $k$ 次操作后还剩下多少节点。

特殊情况:

  • 对空树进行操作时不改变任何东西。

  • 对一个顶点的树进行操作时会移除这个顶点(这个顶点被当作一个叶子)。

  • 对有两个顶点的树进行操作时将删除两个顶点(两个顶点都被当作叶子处理)。

解题思路

看一下题,脑海中大概是一个从外层逐渐蚕食这棵树的过程。

每个点被删除当且仅当这个点只剩下了与父亲的一条边(叶子结点)或者一条边都不剩(根的特殊情况)。

这玩意儿明显是个拓扑排序。

我们在开始时把树的所有叶子结点入队,每次发现删去当前点后与其相连的点度数 $\le 1$,将其入队即可。

然后对每个点设置一个 $dep$ 值表示第一次被删掉的时候是操作了几次。初始值是一开始入队的点 $dep$ 值为 $1$。

最后只需要统计有多少个 $dep$ 值 $>k$ 的点即可。

我的代码里要特判 $n=1$ 的情况大概是因为开始入队时写丑了,写的是deg[i]==1,没有把单独的一个根节点入队(

不过特判一下总没错(

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=400005;
const int inf=100000000000000005;

struct Edge{
    int vet,nxt;
}e[N<<1];

int n,k,edge=0,head[N];
int deg[N],dep[N];
bool inq[N];
queue <int> Q;

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline void addedge(int x,int y){
    e[++edge].vet=y;
    e[edge].nxt=head[x];
    head[x]=edge;
}

signed main(){
//  freopen("CF1593E.in","r",stdin);
//  freopen("CF1593E.out","w",stdout);
    int T=read();
    while (T--){
        n=read(),k=read();
        if (n==1){
            if (k>=1) printf("0\n");
            else printf("1\n");
            continue;
        }
        edge=0; for (int i=1;i<=n;++i) head[i]=0,deg[i]=0;
        for (int i=1;i<=n-1;++i){
            int x=read(),y=read();
            addedge(x,y);
            addedge(y,x);
            ++deg[x],++deg[y];
        }
        while (!Q.empty()) Q.pop();
        for (int i=1;i<=n;++i) dep[i]=inf,inq[i]=false;
        for (int i=1;i<=n;++i)
            if (deg[i]==1){ Q.push(i); inq[i]=true; dep[i]=1; }
        while (!Q.empty()){
            int x=Q.front(); Q.pop();
            // printf("x=%lld dep[x]=%lld\n",x,dep[x]);
            for (int i=head[x];i;i=e[i].nxt){
                int v=e[i].vet;
                // printf("x=%lld v=%lld deg[v]=%lld\n",x,v,deg[v]-1);
                if ((--deg[v])<=1){
                    if (!inq[v]){
                        inq[v]=true;
                        dep[v]=dep[x]+1;
                        Q.push(v);
                    }
                }
            }
        }
        // printf("dep: "); for (int i=1;i<=n;++i) printf("%lld ",dep[i]); printf("\n");
        int ans=0;
        for (int i=1;i<=n;++i)
            if (dep[i]>k) ++ans;
        printf("%lld\n",ans);
    }
    return 0;
}

我们无法选择过去,但我们可以改变未来。