P8616 [蓝桥杯 2014 国 C] 套娃 题解

· · 题解

可以将套娃关系看成一棵树，即将套在大娃中的小娃视为它的儿子。

对于 P 操作的打开套娃，可以看作删除从当前节点父亲到根节点路径上所有点与其他点的连边。

对于询问当前一套娃需要打开多少次才能看到，就是询问他到根节点路径上剩余几条边。

记 dep[i] 表示 i 的深度。

记 fg 数组， fg[i]=1 表示对于 i 节点，他与其父亲的连边已被删除，否则 fg[i]=0。

显然当 fg[i]=1，有 fg[fa_i]=1。即如果它已经被掰出来了，其父亲也一定被掰出来了。

故有对于询问当前一套娃 i 需要打开多少次才能看到，即找到其到根路径上第一个点 u 使有 fg[u]=1，(这个可以用倍增实现)。那么答案就为 dep[u]-dep[i]。

对于修改，也找到 i 其到根路径上第一个点 u 使有 fg[u]=1，从下往上暴力修改， 可以发现每条边至多只会被删一次，所以删除操作的总复杂度是 O(n) 的。

至此，算法总复杂度 O(n\log_2n)，可以通过此题。

code:


#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
    int s=0,f=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=0; c=getchar();}
    while(c>='0'&&c<='9'){s=s*10+c-48; c=getchar();}
    x=f? s:-s;
}
const int N=1e5+10, M=N<<1; int LOGM;
struct edge{int to,nt;} e[M]; int hd[N],ect;
inline void ade(int u,int v){e[++ect]={v,hd[u]}; hd[u]=ect;}

int n,m,rot,in[N],fa[N][22],dep[N];
void pre(int u,int f){
    fa[u][0]=f; dep[u]=dep[f]+1;
    for(int i=1;i<=LOGM;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=hd[u];i;i=e[i].nt) pre(e[i].to,u);
}
bool fg[N];
inline int calc(int x){
    for(int i=LOGM;~i;i--){
        if(fa[x][i] && fg[fa[x][i]]==0) x=fa[x][i];
    }
    return x;
}

signed main(){
    rd(n); rd(m); LOGM=log2(n);
    for(int i=1,u,v;i<n;i++){
        rd(u); rd(v); in[v]++; ade(u,v);
    }
    for(int i=1;i<=n;i++) if(!in[i]){rot=i; break;}
    pre(rot,0); fg[rot]=1;
    for(int i=1;i<=m;i++){
        char c=getchar(); int x;
        while(c!='P'&&c!='Q') c=getchar();
        rd(x);
        if(c=='P'){
            if(fg[x]){
                for(int j=hd[x];j;j=e[j].nt) fg[e[j].to]=1;
                puts("0");
                continue;
            }
            int top=calc(x); top=fa[top][0];
            printf("%d\n",dep[x]-dep[top]);
            for(;;x=fa[x][0]){
                fg[x]=1;
                for(int j=hd[x];j;j=e[j].nt) fg[e[j].to]=1;
                if(x==top) break;
            }
        }
        else{
            if(fg[x]){
                puts("0"); continue;
            }
            int top=calc(x); top=fa[top][0];
            printf("%d\n",dep[x]-dep[top]);
        }
    }
    return 0;
}