SP10707 COT2 - Count on a tree II 莫队

链接

https://vjudge.net/problem/SPOJ-COT2
https://www.luogu.org/problemnew/show/SP10707

思路

dfs欧拉序转化为普通莫队（并不算树上莫队，不过也可做)
好神仙啊，原来欧拉序是可以求任意两点的点，不过要加lca。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m,w[N],now_ans,top;
vector<int> G[N];
int st[N][30],dep[N],belong[N<<1],ans[N];
int lsh[N],a[N<<1],be[N],en[N<<1],T[N];
int js[N];
struct node {
    int l,r,other,id;
    bool operator < (const node &b) const {
        return belong[l]==belong[b.l] ? belong[l]&1 ? r<b.r : r>b.r :belong[l]<belong[b.l];
    }
}Q[N];
void dfs(int u,int f) {
    a[++top]=u;
    be[u]=top;
    for(vector<int>::iterator it=G[u].begin();it!=G[u].end();++it) {
        if(*it==f) continue;
        st[*it][0]=u;
        dep[*it]=dep[u]+1;
        dfs(*it,u);
    }
    a[++top]=u;
    en[u]=top;
}
int lca(int x,int y) {
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=25;i>=0;--i)
        if(dep[st[x][i]]>=dep[y]) x=st[x][i];
    if(x==y) return x;
    for(int i=25;i>=0;--i)
        if(st[x][i]!=st[y][i]) x=st[x][i],y=st[y][i];
    return st[x][0];
}
void add(int x) {
    if(!T[x]) now_ans++;
    T[x]++;
}
void del(int x) {
    T[x]--;
    if(!T[x]) now_ans--;
}
int main() {
    //freopen("a.in","r",stdin);
    n=read(),m=read();
    for(int i=1;i<=n;++i) lsh[i]=w[i]=read();
    sort(lsh+1,lsh+1+n);
    int len=unique(lsh+1,lsh+1+n)-lsh-1;
    for(int i=1;i<=n;++i) w[i]=lower_bound(lsh+1,lsh+1+len,w[i])-lsh;
    for(int i=1;i<n;++i) {
        int x=read(),y=read();
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dep[1]=1;
    dfs(1,0);
    for(int j=1;j<=25;++j) {
        for(int i=1;i<=n;++i) {
            st[i][j]=st[st[i][j-1]][j-1];
        }
    }
    for(int i=1;i<=m;++i) {
        int x=read(),y=read(),z=lca(x,y);
        if(be[x]>be[y]) swap(x,y);
        if(z==x||z==y) {
            Q[i].l=be[x];
            Q[i].r=be[y];
            Q[i].other=0;
        } else {
            Q[i].l=en[x];
            Q[i].r=be[y];
            Q[i].other=z;
        }
        Q[i].id=i;
    }
    int k=sqrt(2*n);
    for(int i=1;i<=2*n;++i) belong[i]=(i-1)/k+1;
    sort(Q+1,Q+1+m);
    for(int i=1,l=1,r=0;i<=m;++i) {
        while(r<Q[i].r) {//add(++r)
            ++r;
            if(js[a[r]])
                del(w[a[r]]);
            else
                add(w[a[r]]);
            js[a[r]]^=1;
        }
        while(l>Q[i].l) {//add(--l)
            --l;
            if(js[a[l]])
                del(w[a[l]]);
            else
                add(w[a[l]]);

            js[a[l]]^=1;
        }
        while(l<Q[i].l) {//del(l++)
            if(js[a[l]])
                del(w[a[l]]);
            else
                add(w[a[l]]);
            js[a[l]]^=1;

            l++;
        }
        while(r>Q[i].r) {//del(r--)
            if(js[a[r]])
                del(w[a[r]]);
            else
                add(w[a[r]]);
            js[a[r]]^=1;

            r--;
        }
        if(Q[i].other)
            add(w[Q[i].other]);
        ans[Q[i].id]=now_ans;
        if(Q[i].other)
            del(w[Q[i].other]);
//      cout<<Q[i].l<<" "<<Q[i].r<<"\n";
    }
    for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}