发布时间：2025-05-22

树分块

在树上随机取$\frac{N}{S}$个点，使得任意两个点之间的距离小于等于$S$

类似树剖的写法

预处理块间信息$f[L,R]$(不包含$L$的信息)，先处理与上一个块的信息$f[K,R]$，复杂度为$O(S)$，暴力处理块间信息，$f[L,R]=f[L,K]+f[K,R]$，复杂度为$\frac{N^2}{S^2}$

总预处理复杂度为$O(N+\frac{N^2}{S^2}*C)$,$C$为合并代价

单次询问的复杂度为$O(2S+\frac{N}{S}+C)$

namespace TopCluster{
    vector<int> siz,mxdep,dep,id,son,par,top;
    vector<vector<int>> adj;
    int S,cnt;// 块大小,关键点个数
    void init(int n){
        siz.assign(n+1,0);
        mxdep.assign(n+1,0);
        dep.assign(n+1,0);
        id.assign(n+1,0);
        son.assign(n+1,0);
        par.assign(n+1,0);
        top.assign(n+1,0);
        adj.assign(n+1,{});
        cnt=0;
    }
    void addEdge(int u,int v){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void dfs1(int u,int fa){
        dep[u]=dep[fa]+1;
        par[u]=fa;
        siz[u]=1;
        mxdep[u]=dep[u];
        for(auto v:adj[u]){
            if(v==fa)continue;
            dfs1(v,u);
            siz[u]+=siz[v];
            mxdep[u]=max(mxdep[u],mxdep[v]);
            if(siz[v]>siz[son[u]])son[u]=v;
        }
        if(mxdep[u]-dep[u]>=S){
            id[u]=++cnt;
            mxdep[u]=dep[u];
        }
        else if(u==1){
            id[u]=++cnt;
        }
    }
    void dfs2(int u,int t){
        top[u]=t;
        if(son[u])dfs2(son[u],t);
        for(auto v:adj[u]){
            if(v==par[u]||v==son[u])continue;
            dfs2(v,v);
        }
    }
    int lca(int u,int v){
        while(top[u]!=top[v]){
            if(dep[top[u]]<dep[top[v]])swap(u,v);
            u=par[top[u]];
        }
        return dep[u]<dep[v]?u:v;
    }
};
using namespace TopCluster; 
bitset<N> f[205][205],now;//f(L,R]，不包含左端点
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> w(n+1),nums;
    for(int i=1;i<=n;i++)cin>>w[i],nums.push_back(w[i]);
    sort(nums.begin(),nums.end());  
    nums.resize(unique(nums.begin(),nums.end())-nums.begin());
    for(int i=1;i<=n;i++)w[i]=lower_bound(nums.begin(),nums.end(),w[i])-nums.begin();
    vector<int> stk;
    S=sqrt(n)+1;
    init(n);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        addEdge(u,v);
    }
    dfs1(1,0);
    dfs2(1,1);
    vector<int> pre(n+1),rk(n+1);// 块i的前驱，以及在链中的排名
    auto dfs=[&](auto dfs,int u,int fa)->void{
        // O(N+(N/S)^2*C),C为合并f[L,R]的复杂度
        if(id[u]){
            if(stk.size()){
                int L=id[stk.back()],R=id[u];
                for(int x=u;x!=stk.back();x=par[x]){
                    f[L][R].set(w[x]);
                }
                now=f[L][R];
                for(int i=0;i<stk.size()-1;i++){
                    auto &bs=f[id[stk[i]]][R];
                    bs=f[id[stk[i]]][L];
                    bs|=now;
                }
                pre[u]=stk.back();
                rk[u]=rk[stk.back()]+1;
            }
            else{
                pre[u]=0;
                rk[u]=1;
            }
            stk.push_back(u);
        }
        for(auto v:adj[u]){
            if(v==fa)continue;
            dfs(dfs,v,u);
        }
        if(id[u])stk.pop_back();
    };
    dfs(dfs,1,0);
    auto cal=[&](int u,int v){
        // 复杂度O(2S+N/S+C),C位合并f[L,R]的复杂度
        int t=lca(u,v);
        now.reset();
        while(u!=t&&!id[u])now.set(w[u]),u=par[u];
        while(v!=t&&!id[v])now.set(w[v]),v=par[v];
        if(u!=t){
            int tmp=u;
            while(dep[pre[tmp]]>=dep[t])tmp=pre[tmp];// 寻找离lca最近的关键点,N/S
            if(tmp!=u)now|=f[id[tmp]][id[u]];
            while(tmp!=t)now.set(w[tmp]),tmp=par[tmp];// 暴力跳S次
        }
        if(v!=t){
            int tmp=v;
            while(dep[pre[tmp]]>=dep[t])tmp=pre[tmp];// 寻找离lca最近的关键点,N/S
            if(tmp!=v)now|=f[id[tmp]][id[v]];
            while(tmp!=t)now.set(w[tmp]),tmp=par[tmp];// 暴力跳S次
        }
        now.set(w[t]);// lca的权值
        return now.count();
    };
    int ans=0;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        u^=ans;
        ans=cal(u,v);
        cout<<ans<<"\n";
    }
}