CF1593E Gardener and Tree（拓扑）题解

· · 题解

题目大意

现在有一棵 $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;
}