自动搬运

查看原文

来自洛谷，原作者为

	Sleepp **

搬运于2025-08-24 21:56:25，当前版本为作者最后更新于2018-09-29 15:42:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

此题树剖裸题，但是并不想写线段树，于是就写了并查集 ，发现好像题解里并没有我这种做法，就写了这篇题解。

题解

我的做法是离线操作，在读入时记录每个点被染色的次数，之后从根节点dfs，如果这个点被染色了，就让并查集数组的值为自己，否则为他的父亲。 然后倒序枚举操作，如果是查询操作，直接find()这个点，得到的值就是最近的被染色的祖先，如果是标记操作，则删除这个标记，即让这个点被染色的次数减1，如果染色次数变成了0，就意味着这个点没有染色了，将并查集数组的值改为它的父亲。

代码

#include <cstdio>
const int MAXN=100010;
struct P {
    bool ty;
    int id,ans;
}p[MAXN];
int edv[MAXN<<1],ednxt[MAXN<<1];
int first[MAXN],cnt=0;
void add(int x,int y) {
    edv[++cnt]=y;
    ednxt[cnt]=first[x];
    first[x]=cnt;
}
int col[MAXN];
char inp[3];
int ufs[MAXN];  //并查集数组
int f[MAXN];	//记录一个点的父亲
void dfs(int x,int fa) {
    if(col[x]) ufs[x]=x;   //如果有染色，就让值等于自己
    else ufs[x]=fa;        //否则等于父亲
    f[x]=fa;
    for(int i=first[x];i;i=ednxt[i]) {
        int v=edv[i];
        if(v==fa) continue;
        dfs(v,x);
    }
}
int find(int x) {
    return x==ufs[x]?x:ufs[x]=find(ufs[x]);
}
int main() {
    int n,q;
    scanf("%d%d",&n,&q);
    int in1,in2;
    for(int i=1;i<n;++i) {
        scanf("%d%d",&in1,&in2);
        add(in1,in2);
        add(in2,in1);
    }
    col[1]=1;
    for(int i=1;i<=q;++i) {
        scanf("%s%d",inp,&p[i].id);
        switch(inp[0]) {
            case 'Q':{
                p[i].ty=0;
                break;
            }
            case 'C':{
                p[i].ty=1;
                ++col[p[i].id];
                break;
            }
        }
    }
    dfs(1,0);
    f[1]=1;
    for(int i=q;i>=1;--i) {
        if(p[i].ty) {
            --col[p[i].id];
            if(!col[p[i].id]) ufs[p[i].id]=f[p[i].id];  //这个点没有染色了
        } else {
            p[i].ans=find(p[i].id);
        }
    }
    for(int i=1;i<=q;++i) {
        if(!p[i].ty) {
            printf("%d\n",p[i].ans);
        }
    }
    return 0;
}

如果强制在线就GG了