发布时间：2024-07-31

SP10707树上计数2(树上莫队板子)

题意：
给定一颗树，每次询问u，v的简单路径上，有多少种颜色
思路：

• 树上问题转序列问题
• 首先获取欧拉序，即dfs序，不过回溯的时候也要加进序列,每个点出现两次
• 对于每个点给一个 $ first_i表示第一次出现，last_i表示第二次出现 $
• 假设 $ first_x<first_y $
  • 如果lca(x,y)=x那么路径出现的点数为 $ [first_x,first_y] $ 出现一次的点
  • 否则为 $ [last_x,first_y] $ 出现一次的点，加上lca

int be[M],block,tot;
vector<int> adj[M];
int w[M],cnt[M];
int first[M],last[M],seq[M],top,dep[M],par[M][20];
bool st[M];
struct Q{
    int id,l,r,p;
};
bool cmp(Q &x,Q &y){
    return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:((be[x.l]&1)?x.r<y.r:x.r>y.r);
}
void dfs(int u,int fa){
    seq[++top]=u;
    first[u]=top;
    dep[u]=dep[fa]+1;
    par[u][0]=fa;
    for(int i=1;i<=__lg(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1];
    for(auto v:adj[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
    seq[++top]=u;
    last[u]=top;
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    while(dep[u]>dep[v])u=par[u][__lg(dep[u]-dep[v])];
    if(u==v)return u;
    for(int i=__lg(dep[u]);i>=0;i--){
        if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
    }
    return par[u][0];
}
void add(int x,int &res){
    st[x]^=1;
    if(!st[x]){
        if(!(--cnt[w[x]]))res--;
    }
    else{
        if(!(cnt[w[x]]++))res++;
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> nums;
    for(int i=1;i<=n;i++)cin>>w[i],nums.push_back(w[i]);
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++)w[i]=lower_bound(nums.begin(),nums.end(),w[i])-nums.begin();
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> ans(m);
    dfs(1,0);
    vector<Q> q;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        if(first[u]>first[v])swap(u,v);
        int p=lca(u,v);
        if(p==u)q.push_back({i,first[u],first[v],0});
        else q.push_back({i,last[u],first[v],p});
    }
    block=sqrt(1.0*top*top/m),tot=(top+block-1)/block;
    for(int i=1;i<=tot;i++){
        int l=(i-1)*block+1,r=min(top,i*block);
        for(int j=l;j<=r;j++)be[j]=i;
    }
    sort(q.begin(),q.end(),cmp);
    int res=0;
    for(int i=0,l=1,r=0;i<m;i++){
        auto [id,ql,qr,p]=q[i];
        while(r<qr)add(seq[++r],res);
        while(r>qr)add(seq[r--],res);
        while(l<ql)add(seq[l++],res);
        while(l>ql)add(seq[--l],res);
        if(p)add(p,res);
        ans[id]=res;
        if(p)add(p,res);
    }
    for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}