SPOJ COT2

把莫队扩展到树上。

给定一棵树,树上每个点有权值,询问一条路径上有多少个不同的点权。

树上莫队板子题。
存个板子。

//SPOJ COT2
//by Cydiater
//2017.3.21
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define up(i,j,n)    for(int i=j;i<=n;++i)
#define down(i,j,n)    for(int i=j;i>=n;--i)
#define cmax(a,b)    a=max(a,b)
#define cmin(a,b)    a=min(a,b)
#define Auto(i,node)    for(int i=LINK[node];i;i=e[i].next)
#define eprintf(...)    fprintf(stderr,__VA_AGRS__)

const int MAXN=1e5+5;
const int oo=0x3f3f3f3f;

int N,M,col[MAXN],root,res[MAXN],ans=0,ccol[MAXN];
struct edge{
    int y,next;
}e[MAXN];

namespace Graph{
    int LINK[MAXN],len=0,sta[MAXN],tp,dfn[MAXN];
    int fa[MAXN][25],dep[MAXN],blo[MAXN],B,cnt,dfsclock;
    bool vis[MAXN];

    inline void insert(int x,int y){
        e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;
    }
    inline void Insert(int x,int y){
        insert(x,y);
        insert(y,x);
    }
    void DFS(int node,int deep,int father){
        fa[node][0]=father;dep[node]=deep;
        dfn[node]=++dfsclock;
        int bt=tp;
        Auto(i,node)if(e[i].y!=father){
            DFS(e[i].y,deep+1,node);
            if(tp-bt>=B){
                cnt++;
                while(tp!=bt)blo[sta[tp--]]=cnt;
            }
        }
        sta[++tp]=node;
    }
    void GetAnc(){
        up(i,1,15)up(node,1,N)if(fa[node][i-1])
            fa[node][i]=fa[fa[node][i-1]][i-1];
    }
    int LCA(int x,int y){
        if(x==y)    return x;
        if(dep[x]<dep[y])swap(x,y);
        down(i,15,0)if(dep[x]-(1<<i)>=dep[y])
            x=fa[x][i];
        if(x==y)    return x;
        down(i,15,0)if(fa[x][i]&&fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
        return fa[x][0];
    }
    void rev(int k){
        if(vis[k]){
            vis[k]=0;
            ccol[col[k]]--;
            if(ccol[col[k]]==0)ans--;
        }else{
            vis[k]=1;
            ccol[col[k]]++;
            if(ccol[col[k]]==1)ans++;
        }
    }
    void Go(int x,int y){
        while(x!=y){
            if(dep[x]>dep[y]){
                rev(x);x=fa[x][0];
            }else{
                rev(y);y=fa[y][0];
            }
        }
    }
}using namespace Graph;

struct Query{
    int x,y,p;
    bool operator < (const Query &t) const {
        return blo[x]==blo[t.x]?dfn[y]<dfn[t.y]:blo[x]<blo[t.x];
    }
}qry[MAXN];


int num[MAXN],top=0;
namespace solution{
    void Prepare(){
        scanf("%d%d",&N,&M);
        up(i,1,N){
            scanf("%d",&col[i]);
            num[++top]=col[i];
        }
        sort(num+1,num+top+1);
        top=unique(num+1,num+top+1)-(num+1);
        up(i,1,N)col[i]=lower_bound(num+1,num+top+1,col[i])-num;
        B=sqrt(N*2);
        up(i,2,N){
            int x,y;
            scanf("%d%d",&x,&y);
            Insert(x,y);
        }
        DFS(1,0,0);
        while(tp)blo[sta[tp--]]=cnt;
        GetAnc();
        up(i,1,M){
            int x,y;
            scanf("%d%d",&x,&y);
            if(dfn[x]>dfn[y])swap(x,y);
            qry[i]=(Query){x,y,i};
        }
        sort(qry+1,qry+M+1);
        Go(qry[1].x,qry[1].y);
        int tmp=LCA(qry[1].x,qry[1].y);
        rev(tmp);
        res[qry[1].p]=ans;
        rev(tmp);
    }
    void Solve(){
        up(i,2,M){
            Go(qry[i-1].x,qry[i].x);
            Go(qry[i-1].y,qry[i].y);
            int tmp=LCA(qry[i].x,qry[i].y);
            rev(tmp);
            res[qry[i].p]=ans;
            rev(tmp);
        }
        up(i,1,M)printf("%d\n",res[i]);
    }
}

int main(){
    using namespace solution;
    Prepare();
    Solve();
    return 0;
}