spoj COT2(树上莫队)

模板。树上莫队的分块就是按dfn分，然后区间之间转移时注意一下就好。有个图方便理解http://blog.csdn.net/thy_asdf/article/details/47377709；

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

int ccc[maxn],col[maxn],n,m,last[maxn],pre[maxn*],other[maxn*],d[maxn],bel[maxn],f[maxn][];

int res,bo,ind,dfn[maxn],ans[maxn*],t,cnt,sta[maxn],top,vis[maxn],tong[maxn],ttt[maxn];

struct que{

    int u,v,id;

    bool operator<(const que&tmp)const{

        if(bel[u]==bel[tmp.u])return dfn[v]<dfn[tmp.v];

        return bel[u]<bel[tmp.u];

    }

}q[maxn*];

void add(int x,int y){++t;pre[t]=last[x];last[x]=t;other[t]=y;}

int dfs(int x){

    int siz=;

    dfn[x]=++ind;

    for(int i=last[x];i;i=pre[i]){

        int v=other[i];

        if(v==f[x][])continue;

        d[v]=d[x]+;f[v][]=x;

        siz+=dfs(v);

        if(siz>=bo){

            ++cnt;

            for(int j=;j<=siz;++j)

            bel[sta[top--]]=cnt;

            siz=;

        }

    }

    sta[++top]=x;

    return siz+;

}

void change(int x){

    if(!vis[x]){vis[x]=;tong[col[x]]++;if(tong[col[x]]==)res++;}

    else{vis[x]=;tong[col[x]]--;if(tong[col[x]]==)res--;}

}

void solve(int u,int v){

    while(u!=v){

        if(d[u]>d[v])change(u),u=f[u][];

        else change(v),v=f[v][];

    }

}

int lca(int x,int y){

    if(d[x]<d[y])swap(x,y);

    for(int i=;i>=;--i)

    if(d[f[x][i]]>=d[y])x=f[x][i];

    if(x==y)return x;

    for(int i=;i>=;--i)

    if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];

    return f[x][];

}

int main(){

    cin>>n>>m;

    int x,y;bo=sqrt(n+0.5);

    for(int i=;i<=n;++i){

        scanf("%d",&ccc[i]);

        ttt[i]=ccc[i];

    }

    sort(ttt+,ttt+n+);

    int len=unique(ttt+,ttt+n+)-ttt-;

    for(int i=;i<=n;++i){

        col[i]=lower_bound(ttt+,ttt+len+,ccc[i])-ttt;

    }

    for(int i=;i<n;++i){

        scanf("%d%d",&x,&y);

        add(x,y);add(y,x);

    }

    d[]=;dfs();

    ++cnt;

    while(top)bel[sta[top--]]=cnt;

    for(int j=;j<=;++j)

      for(int i=;i<=n;++i)

        f[i][j]=f[f[i][j-]][j-];

    for(int i=;i<=m;++i){

        q[i].id=i;

        scanf("%d%d",&q[i].u,&q[i].v);

        if(dfn[q[i].u]>dfn[q[i].v])swap(q[i].u,q[i].v);

    }

    sort(q+,q+m+);

    int op=lca(q[].u,q[].v);

    solve(q[].u,q[].v);

    change(op);ans[q[].id]=res;change(op);

    for(int i=;i<=m;++i){

        solve(q[i-].u,q[i].u);solve(q[i-].v,q[i].v);

        op=lca(q[i].u,q[i].v);

        change(op);ans[q[i].id]=res;change(op);

    }

    for(int i=;i<=m;++i){

        printf("%d\n",ans[i]);

    }

    //system("pause");

    return ;

}