简易树分块

· · 题解

相信大家都会 \text{Top cluster} 分解吧，其实任何的树分块都可以通过随机撒点解决，如果强行需要形成簇的话还需要建一棵虚树。

但本题并不需要形成簇，所以只要随机选取 \sqrt n 个节点作为关键点，然后处理任意两点之间路径上所有点颜色 bitset，查询时只需要将路径上最左和最右的关键点取出，边块暴力即可。

虽然这样的空间复杂度十分的劣质，但还是足以通过。

空间复杂度 O(\dfrac{n^2}w)，时间 O(\dfrac{n^2+nq}w)，由于撒的点不多，并且随机不够严格，所以常数较大：

#include<bits/stdc++.h>
using namespace std;
const int N=4e4+4;
using bt=bitset<N>;
bt tb[205][205],nw;
#define tp(x) (t[f[x]][1]==x)
#define in(x) (t[f[x]][0]==x||tp(x))
#define ls t[x][0]
#define rs t[x][1]
int v[N],n,q,mp[N],m,ct[N],ans;
int p[N],dfn[N],dlt,rt,cl[N];
vector<int>lk[N];
namespace lct{
    int f[N],t[N][2],sm[N];
    bt rv;
    void pp(int x){
        sm[x]=sm[ls]|sm[rs]|cl[x];
    }void rev(int x){
        swap(ls,rs),rv[x]=!rv[x];
    }void pd(int x){
        if(rv[x]){
            if(ls)rev(ls);
            if(rs)rev(rs);rv[x]=0;
        }
    }void ppd(int x){
        if(in(x))ppd(f[x]);pd(x);
    }
    void rot(int x){
        int y=f[x],k=tp(x),w=t[x][!k];
        // cerr<<x<<" "<<y<<" "<<w<<endl;
        // cerr<<f[x]<<" "<<f[y]<<endl;
        t[f[w]=t[x][!k]=y][k]=w;
        if(in(y))t[f[y]][tp(y)]=x;
        f[x]=f[y],f[y]=x,pp(y);
        assert(x!=f[x]&&y!=f[y]);
    }
    void splay(int x){
        ppd(x);for(int z=f[x];in(x);rot(x),z=f[x])
            if(in(z))rot(tp(x)^tp(z)?x:z);pp(x);
    }
    int acs(int x){
        int y,z;
        for(y=0;x;x=f[y=x])
            splay(x),rs=y,pp(x);
        return y;
    }
    int getl(int x){
        while(1){assert(x);
            pd(x);
            if(sm[ls])x=ls;
            else if(cl[x])break;
            else x=rs;
        }splay(x);
        return x;
    }
    int getr(int x){
        while(1){assert(x);
            pd(x);
            if(sm[rs])x=rs;
            else if(cl[x])break;
            else x=ls;
        }splay(x);return x;
    }
    void dfs(int x){
        // printf("dfs:%d\n",x);
        nw[::v[x]]=1;
        if(ls)dfs(ls);
        if(rs)dfs(rs);
    }
    int solve(int x,int y){
        acs(x),splay(x),rev(x);
        // cerr<<"lrs:"<<ls<<" "<<rs<<endl;
        acs(y),splay(x);
        nw.reset();
        if(sm[x]){
            int l=getl(x);
            if(t[l][0])dfs(t[l][0]);
            int r=getr(l);
            // printf("l:%d r:%d\n",l,r);
            if(t[r][1])dfs(t[r][1]);
            nw|=tb[cl[l]][cl[r]];
        }else dfs(x);
        return nw.count();
    }
}
void dfs(int x,int rp){
    dfn[x]=++dlt;
    for(int y:lk[x])
        if(y!=rp)
            dfs(y,x),lct::f[y]=x/*,cerr<<"set:"<<x<<" "<<y<<endl*/;
}
void dfs2(int x,int rp){
    ++ct[v[x]],nw[v[x]]=1;
    if(cl[x])tb[rt][cl[x]]=nw;
    for(int y:lk[x])
        if(y!=rp)dfs2(y,x);
    if(!--ct[v[x]])nw[v[x]]=0;
}
int main(){
    ios::sync_with_stdio(false);
    mt19937_64 rg(random_device{}());
    cin>>n>>q;
    int i,x,y;
    for(x=1;x<=n;++x)cin>>v[x],mp[x]=v[x];
    for(i=1;i<n;++i){
        cin>>x>>y;
        lk[x].push_back(y);
        lk[y].push_back(x);
    }sort(mp+1,mp+n+1),dfs(1,0);
    m=unique(mp+1,mp+n+1)-mp;
    for(x=1;x<=n;++x)
        v[x]=lower_bound(mp+1,mp+m,v[x])-mp,p[x]=x;
    shuffle(p+1,p+n+1,rg),m=1+sqrt(1+n);
    if(m>n)m=n;
    for(i=1;i<=m;++i)cl[p[i]]=i;
    for(rt=1;rt<=m;++rt)dfs2(p[rt],0);
    // for(x=1;x<=m;++x)printf("%d%c",p[x]," \n"[x==m]);
    // m=0;
    while(q--){
        cin>>x>>y,x^=ans;
        ans=lct::solve(x,y);
        printf("%d\n",ans);
    }return 0;
}