T3 牛半仙的妹子Tree

看见数据规模

$n,m \leq 10^5$

秒想到 $O(n\sqrt{n})$ 的分块

我们用操作 $2$ 把所以询问分成多个子问题（块）

对于大小大于 $\sqrt m$ 的块我们用 $bfs$ 处理，每次 $O(n)$ 处理，均摊每个操作 $O(\sqrt n)$

对于大小小于 $\sqrt m$ 的块我们算出块内每个修改 $1$ 对查询 $2$ 的贡献，每个修改与询问的贡献计算 $2$ 次离线下来，用 $tarjan$ 算出，每个询问 $O(\sqrt m)$

综合下来，时间复杂度为 $O(m(\sqrt n+\sqrt m))$

#include<bits/stdc++.h>
using namespace std;
# define Type template<typename T>
# define ll long long
# define read read1<ll>()
Type T read1(){
    T t=0;char k;
    bool v=0;
    do (k=getchar())=='-'&&(v=1);while('0'>k||k>'9');
    while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
    return v?-t:t;
}
int s,m,opt[100005],x[100005],ne[100005];
vector<int>G[100005],Q[100005],W[100005],N[100005];
bool ans[100005],vis[100005];
queue<int>q;
void Get(int l,int r){
    while(!q.empty())q.pop();
    memset(vis,0,sizeof(vis));
    for(int i=l;i<=r;++i){
        int cnt=q.size();
        while(cnt--){
            int n=q.front();q.pop();
            for(int j=0;j<G[n].size();++j)
                if(!vis[G[n][j]]){
                    vis[G[n][j]]=1;
                    q.push(G[n][j]);
                }
        }
        if(opt[i]==1&&!vis[x[i]])q.push(x[i]),vis[x[i]]=1;
        if(opt[i]==3)ans[i]|=vis[x[i]];
    }
}
int f[100005],h[100005];
int Find(int x){return f[x]==x?x:f[x]=Find(f[x]);}
bool Root(int x){return f[x]==x;}
void dfs(int n,int fa){
    h[n]=h[fa]+1;//cout<<n<<endl;
    for(int i=0;i<G[n].size();++i)
        if(G[n][i]^fa)
            dfs(G[n][i],n);
    for(int i=0;i<Q[n].size();++i)
        if(Root(Q[n][i])){
            Q[Q[n][i]].push_back(n);
            W[Q[n][i]].push_back(W[n][i]);
            N[Q[n][i]].push_back(N[n][i]);
        }
        else{
            int w=Find(Q[n][i]);
            ans[N[n][i]]|=(h[n]+h[Q[n][i]]-h[w]*2)<=W[n][i];
        }
    f[Find(n)]=fa;
}
int main(){
    // freopen("tgT3.in","r",stdin);
    // freopen("tgT3.ans","w",stdout);
    s=read,m=read;  
    for(int i=1;i<s;++i){
        int u=read,v=read;
        G[u].push_back(v);
        G[v].push_back(u);
    }for(int i=1;i<=s;++i)f[i]=i;
    for(int i=1;i<=m;++i)
        opt[i]=read,x[i]=read;
    ne[m+1]=m+1;
    for(int i=m;i>=1;--i){
        ne[i]=ne[i+1];
        if(opt[i]==2)ne[i]=i;
    }
    int b=sqrt(m);
    for(int i=1;i<=m;++i)
        if(opt[i]==1)
            if(ne[i]-i>b){
                Get(i,ne[i]-1);
                i=ne[i];
                continue;
            }
            else{
                for(int k=i;k<ne[i];++k)
                    if(opt[k]==1)
                        for(int j=k+1;j<ne[i];++j)
                            if(opt[j]==3)
                                if(x[k]==x[j])
                                    ans[j]=1;
                                else Q[x[k]].push_back(x[j]),W[x[k]].push_back(j-k),N[x[k]].push_back(j);
                i=ne[i];
            }
    dfs(1,0);
    for(int i=1;i<=m;++i)
        if(opt[i]==3)
            puts(ans[i]?"wrxcsd":"orzFsYo");
    return 0;
}