题目链接：http://www.spoj.com/problems/COT2/
参考博客：http://www.cnblogs.com/xcw0754/p/4763804.html
上面这个人推导部分写的简洁明了，方便理解，但是最后的分情况讨论有些迷，感觉是不必要的，更简洁的思路看下面的博客
传送门：http://blog.****.net/kuribohg/article/details/41458639
题意是这样的，给你一棵无根树，给你m个查询，每次查询输出节点x到节点y路径上不同颜色的节点有多少个（包括xy）
没什么说的，直接上代码吧
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int const MAX_N=+;
int const MAX_M=+;
int n,m,ans,nowLca,lastL,lastR,tempAns;
int color[MAX_N];
vector<int> allColor;
vector<int>::iterator it;
int lin[MAX_N],e_cnt;
struct Query{
int x;
int y;
int id;
int ans;
}query[MAX_M];
struct Edge{
int next;
int y;
}e[*MAX_N];
void insert(int u,int v){
e[++e_cnt].next=lin[u];
e[e_cnt].y=v;
lin[u]=e_cnt;
}
int b_len,b_cnt,bk[MAX_N];
int fa[MAX_N][],deep[MAX_N];
int n_cnt,dfn[MAX_N],top,stack[MAX_N];
bool vis[MAX_N];
void dfs(int u){
dfn[u]=++n_cnt;
int btm=top;
for(int i=lin[u];i;i=e[i].next){
int v=e[i].y;
if(!dfn[v]){
fa[v][]=u;
deep[v]=deep[u]+;
dfs(v);
if(top-btm>=b_len){
b_cnt++;
while(top>btm){
bk[stack[top--]]=b_cnt;
}
}
}
}
stack[++top]=u;
}
bool queryCmp_xkb_ydfn(Query a,Query b){
if(bk[a.x]==bk[b.x])return dfn[a.y]<dfn[b.y];
return bk[a.x]<bk[b.x];
}
bool queryCmp_id(Query a,Query b){
return a.id<b.id;
}
int lca(int u,int v){
if(deep[u]<deep[v])swap(u,v);
for(int i=;~i;i--)
if(deep[fa[u][i]]>=deep[v])
u=fa[u][i];
if(u == v) return u;
for(int i=;~i;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][];
}
int c_cnt[MAX_N];
void MoveToLca(int u){
for(;u!=nowLca;u=fa[u][]){
if(vis[u]){
vis[u]=false;
c_cnt[color[u]]--;
if(!c_cnt[color[u]])ans--;
}else{
vis[u]=true;
if(!c_cnt[color[u]])ans++;
c_cnt[color[u]]++;
}
}
}
int GetAns(int x,int u,int v){
int tlca=lca(u,v);
if(c_cnt[color[tlca]])return x;
else return x+;
} void FirstMo(){
int L=query[].x,R=query[].y;
nowLca=lca(L,R);
MoveToLca(L);
MoveToLca(R);
query[].ans=GetAns(ans,L,R);
lastL=L;lastR=R;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
allColor.clear();
//read colors
for(int i=;i<=n;i++){
scanf("%d",&color[i]);
allColor.push_back(color[i]);
}
//Discretization the color
sort(allColor.begin(),allColor.end());
it=unique(allColor.begin(),allColor.end());
allColor.resize(distance(allColor.begin(),it));
for(int i=;i<=n;i++){
color[i]=lower_bound(allColor.begin(),allColor.end(),color[i])-allColor.begin()+;
}
//read the tree
memset(lin,,sizeof(lin));
e_cnt=;
for(int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
insert(u,v);
insert(v,u);
}
//divide in blocks
//prepare for lca: get deep, dfs order, get father
b_len=sqrt((double)n);
b_cnt=;
n_cnt=;
top=;
deep[]=,deep[]=;
memset(fa,,sizeof(fa));
memset(dfn,,sizeof(dfn));
memset(vis,,sizeof(vis));
memset(stack,,sizeof(stack));
dfs();
b_cnt++;
while(top){
bk[stack[top--]]=b_cnt;
}
for(int i = ; (<<i) <= n; i++)
for(int j = ; j <= n; j++)
fa[j][i] = fa[fa[j][i-]][i-];
//read the query
for(int i=;i<=m;i++){
scanf("%d%d",&query[i].x,&query[i].y);
query[i].id=i;
if(dfn[query[i].x]>dfn[query[i].y])
swap(query[i].x,query[i].y);
}
//mo's algorithm
sort(query+,query+m+,queryCmp_xkb_ydfn);
memset(vis,,sizeof(vis));
memset(c_cnt,,sizeof(c_cnt));
lastL=,lastR=,ans=;
for(int i=;i<=m;i++){
int L=query[i].x,R=query[i].y;
nowLca=lca(L,lastL);
MoveToLca(L);
MoveToLca(lastL);
nowLca=lca(R,lastR);
MoveToLca(R);
MoveToLca(lastR);
query[i].ans=GetAns(ans,L,R);
lastL=L;lastR=R;
}
sort(query+,query+m+,queryCmp_id);
for(int i=;i<=m;i++){
printf("%d\n",query[i].ans);
}
}
return ;
}
wa了无数发，最后发现是dfs的时候用vis数组判断点是否访问过，结果忘记初始化vis[1]了。。。。好蠢，后来改成了直接用dfn数组判断是否访问过了，本意是节省资源，结果居然A了。。。人生处处是惊喜。
这里顺便总结下lca写法吧。
这里的是倍增法求LCA
int fa[MAX_N][20],deep[MAX_N];
int dfn[MAX_N];void dfs(int u){
dfn[u]=++n_cnt;
for(int i=lin[u];i;i=e[i].next){
int v=e[i].y;
if(!dfn[v]){
fa[v][0]=u;
deep[v]=deep[u]+1;
dfs(v);
}
}
}
int lca(int u,int v){
if(deep[u]<deep[v])swap(u,v);
for(int i=17;~i;i--)
if(deep[fa[u][i]]>=deep[v])
u=fa[u][i];
if(u == v) return u;
for(int i=17;~i;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}int main()
{
n_cnt=0;
deep[0]=0,deep[1]=1;
memset(fa,0,sizeof(fa));
memset(dfn,0,sizeof(dfn));
dfs(1);for(int i = 1; (1<<i) <= n; i++)
for(int j = 1; j <= n; j++)
fa[j][i] = fa[fa[j][i-1]][i-1];
return 0;
}
dfn换成vis也是一样的
首先初始化deep数组表示节点深度，然后是fa[i][j]表示节点i的第2^j的父亲节点是什么，
先dfs求出deep和直系父亲
然后双重循环处理fa数组
lca的时候，先对齐u和v，就是让他们处于同一深度，然后一起向上，直到lca的儿子为止，返回他的父亲，就是lca。