预处理dfs序，询问转为区间1的个数，用可持久化bitset预处理出所有可能的修改对应哪些位置，然后用一个bitset维护当前每个点的状态，修改时可以用xor实现
#include<bits/stdc++.h> int _(){ int x=0,c=getchar(); while(c<48)c=getchar(); while(c>47)x=x*10+c-48,c=getchar(); return x; } const int N=55007; typedef unsigned long long u64; typedef u64 block[32]; typedef block *bits[32]; block pool[N*3],*pp=pool; int n,m,q,fa[N],son[N],dep[N],dl[N],dr[N],cb; std::vector<int>e[N]; int dfn[N],mxd[N],tk=0; bits f[N],fl[N],fr[N]; void init(){ std::queue<int>q; q.push(1);dep[1]=1; while(q.size()){ int w=q.front();q.pop(); for(unsigned i=0;i<e[w].size();++i){ int u=e[w][i]; if(!dep[u])q.push(u),fa[u]=w,dep[u]=dep[w]+1; else if(dep[u]==dep[w]&&w<u){ for(int x=w,y=u,x0=u,y0=w;x!=y;x=fa[x],y=fa[y]){ dl[x]=dr[y]=1; son[x]=x0,son[y]=y0; x0=x,y0=y; } } } } } void dfs(int w){ dfn[w]=++tk; for(unsigned i=0;i<e[w].size();++i){ int u=e[w][i]; if(dep[u]>dep[w]&&u!=son[w])dfs(u); } mxd[w]=tk; if(dep[son[w]]>dep[w]&&son[w])dfs(son[w]); } void cpy(bits a,bits b,int x){ for(int i=0;i<cb;++i)a[i]=b[i]; memcpy(a[x>>11]=++pp,b[x>>11],sizeof(block)); (*pp)[x>>6&31]|=1llu<<(x&63); } void get(int w){ if(f[w][0])return; get(fa[w]); cpy(f[w],f[fa[w]],dfn[w]); } void getr(int); void getl(int w){ if(fl[w][0])return; int u=dr[w]?son[w]:fa[w]; if(u==fa[w]&&w!=son[u]){ dl[u]?getr(u):getl(u); cpy(fl[w],dl[u]?fr[u]:fl[u],dfn[w]); }else{ getl(u); cpy(fl[w],fl[u],dfn[w]); } } void getr(int w){ if(fr[w][0])return; int u=dl[w]?son[w]:fa[w]; if(u==fa[w]&&w!=son[u]){ dl[u]?getr(u):getl(u); cpy(fr[w],dl[u]?fr[u]:fl[u],dfn[w]); }else{ getr(u); cpy(fr[w],fr[u],dfn[w]); } } u64 ans[5007]; int test(int x){ return ans[x>>6]>>(x&63)&1; } int q0(int l,int r){ int l1=l>>6,r1=r>>6,s=0; if(l1==r1)for(int i=l;i<=r;++i)s+=test(i); else{ for(int i=l;(i>>6)==l1;++i)s+=test(i); for(int i=r;(i>>6)==r1;--i)s+=test(i); for(int i=l1+1;i<r1;++i){ u64 x=ans[i]; s+=__builtin_popcount(x&0xffffffff); s+=__builtin_popcount(x>>32); } } return r-l+1-s; } void rev(bits w){ u64*A=ans,*B; for(int i=0;i<cb;++i){ B=*(w[i]); for(int j=0;j<32;j+=8){ A[0]^=B[0];A[1]^=B[1];A[2]^=B[2];A[3]^=B[3]; A[4]^=B[4];A[5]^=B[5];A[6]^=B[6];A[7]^=B[7]; A+=8,B+=8; } } } int main(){ n=_();m=_();q=_(); cb=(n+1>>11)+1; for(int i=0;i<cb;++i)f[0][i]=fl[0][i]=fr[0][i]=pp; for(int i=1,a,b;i<=m;++i){ a=_();b=_(); e[a].push_back(b); e[b].push_back(a); } init(); dfs(1); for(int i=1;i<=n;++i){ get(i); getl(i); getr(i); } for(int i=1;i<=q;++i){ int op=_(),x=_(); if(op==1)rev(f[x]); else if(op==2)rev(dl[x]?fr[x]:fl[x]); else printf("%d ",q0(dfn[x],mxd[x])); } return 0; }