SPOJ 10707 COT2 - Count on a tree II

思路

树上莫队的题目
每次更新(u1,u2)和(v1,v2)（不包括lca）的路径，最后单独统计LCA即可

代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
int v[100100*2],fir[100100],nxt[100100*2],cnt=0,w_p[100100],b[100100],n,m,tx,sum,jump[100100][20],dep[100100],in_ans[100100],sz,belong[100100],block_cnt,ans[100100],color[100100],U,V;
stack S;
void addedge(int ui,int vi){
    ++cnt;
    v[cnt]=vi;
    nxt[cnt]=fir[ui];
    fir[ui]=cnt;
}
void dfs(int u,int f){
    jump[u][0]=f;
    for(int i=1;i<20;i++)
        jump[u][i]=jump[jump[u][i-1]][i-1];
    dep[u]=dep[f]+1;
    int t=S.size();
    for(int i=fir[u];i;i=nxt[i]){
        if(v[i]==f)
            continue;
        dfs(v[i],u);
        if(S.size()-t>=sz){
            ++block_cnt;
            while(S.size()>t){
                belong[S.top()]=block_cnt;
                S.pop();
            }
        }
    }
    S.push(u);
}
void init(void){
    sz=sqrt(n);
    dfs(1,0);
}
int lca(int x,int y){
    if(dep[x]=0;i--)
        if(dep[jump[x][i]]>=dep[y])
            x=jump[x][i];
    if(x==y)
        return x;
    for(int i=19;i>=0;i--)
        if(jump[x][i]!=jump[y][i])
             x=jump[x][i],y=jump[y][i];
    return jump[x][0];
}
void modi_point(int x){
    if(in_ans[x]){//erase
        color[w_p[x]]--;
        if(!color[w_p[x]])
            sum--;
    }
    else{
        if(!color[w_p[x]])
            sum++;
        color[w_p[x]]++;
    }
    in_ans[x]^=1;
}
void move_path(int x,int y){//(x,y) except LCA(x,y)
    if(dep[x]dep[y]){
        modi_point(x);
        x=jump[x][0];
    }
    while(x!=y){
        modi_point(x);
        modi_point(y);
        x=jump[x][0];
        y=jump[y][0];
    }
}
struct Query{
    int u,v,id;
    bool operator < (const Query &b) const{
        return (belong[u]==belong[b.u])?belong[v]