题目链接
HYSBZ - 2243
题目
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），
如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
Input
第一行包含2个整数n和m，分别表示节点数和操作数；
第二行包含n个正整数表示n个节点的初始颜色
下面 行每行包含两个整数x和y，表示x和y之间有一条无向边。
下面 行每行描述一个操作：
“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；
“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。
Output
对于每个询问操作，输出一行答案。
Sample Input
6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5
Sample Output
3
1
2
Hint
数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。
分析
解决树上路径的修改、查询问题，很容易联想到用树链剖分将路径剖分成连续的区间去解决。
问题的关键是用数据结构（线段树、树状数组等）去维护区间信息。
这题比较恶心的就是要维护区间合并，当两个区间合并时，需要手动判断一下是否合并处颜色一致。
AC代码
#include <bits/stdc++.h>
#define lson p*2
#define rson (p*2+1)
using namespace std;
const int maxn=1e5+100;
vector<int> g[maxn];
int n,m,cnt;
int a[maxn],initcol[maxn];
int son[maxn],dep[maxn],fa[maxn],sz[maxn];
int top[maxn],id[maxn],pos[maxn];//线段树维护区间覆盖颜色、区间查询颜色段数
struct node
{int l,r,lc,rc,mark,num;
}T[maxn<<2];void down(int p)
{if(T[p].l==T[p].r) return ;//叶子结点终止if(T[p].mark==0) return ;//标记为空，无需向下修改T[p*2].rc=T[p*2].lc=T[p*2+1].rc=T[p*2+1].lc=T[p].mark;T[p*2].mark=T[p*2+1].mark=T[p].mark;T[p].mark=0;T[p*2].num=T[p*2+1].num=1;return ;
}
void up(int p)
{T[p].lc=T[p*2].lc;T[p].rc=T[p*2+1].rc;T[p].num=T[p*2].num+T[p*2+1].num-(T[p*2].rc==T[p*2+1].lc);return ;
}
void build(int p,int l,int r)
{T[p].l=l,T[p].r=r;T[p].lc=initcol[l];T[p].rc=initcol[r];T[p].mark=0;if(l==r){T[p].num=1;return ;}int mid=(l+r)>>1;build(lson,l,mid);build(rson,mid+1,r);up(p);return ;
}
void update(int p,int x,int y,int c)//覆盖区间[x,y]为c
{if(T[p].l==x && T[p].r==y){T[p].lc=T[p].rc=c;T[p].mark=c;T[p].num=1;return ;}down(p);int mid=(T[p].l+T[p].r)>>1;if(y<=mid) update(lson,x,y,c);else if(x>mid) update(rson,x,y,c);else{update(lson,x,mid,c);update(rson,mid+1,y,c);}up(p);return ;
}
int query(int p,int x,int y)//查询区间[x,y]的颜色段数
{if(T[p].l==x && T[p].r==y) return T[p].num;down(p);int mid=(T[p].l+T[p].r)>>1;int ans=0;//没有区间合并操作if(y<=mid) return query(p*2,x,y);else if(x>mid) return query(p*2+1,x,y);else{//有区间合并操作return query(p*2,x,mid)+query(p*2+1,mid+1,y)-(T[lson].rc==T[rson].lc);}
}
int color(int p,int x)//查询x结点的颜色
{if(x==T[p].l) return T[p].lc;if(x==T[p].r) return T[p].rc;down(p);int mid=(T[p].l+T[p].r)>>1;if(x<=mid) return color(lson,x);else return color(rson,x);
}
//树链剖分void dfs1(int u,int f,int d)
{dep[u]=d;fa[u]=f;sz[u]=1;for(int i=0;i<g[u].size();i++){int v=g[u][i];if(v==f) continue;dfs1(v,u,d+1);sz[u]+=sz[v];if(son[u]==-1 || sz[v]>sz[son[u]])son[u]=v;}
}void dfs2(int u,int topf)
{top[u]=topf;id[u]=++cnt;initcol[id[u]]=a[u];if(son[u]==-1) return ;dfs2(son[u],topf);for(int i=0;i<g[u].size();i++){int v=g[u][i];if(v==fa[u] || v==son[u]) continue;dfs2(v,v);}
}
int qPath(int x,int y)//查询路径x-->y的颜色段数
{int ans=0,f1=top[x],f2=top[y];while(f1!=f2){if(dep[f1]<dep[f2]){swap(f1,f2);swap(x,y);}int L=id[f1],R=id[x];//注意判断两个区间相邻处的颜色是否一样ans+=query(1,L,R)-(color(1,id[f1])==color(1,id[fa[f1]]));x=fa[f1];f1=top[x];}if(dep[x]>dep[y]) swap(x,y);int L=id[x],R=id[y];ans+=query(1,L,R);return ans;
}
void cPath(int x,int y,int c)//将路径x-->y上的所有结点染色
{int f1=top[x],f2=top[y];while(f1!=f2){if(dep[f1]<dep[f2]){swap(f1,f2);swap(x,y);}update(1,id[f1],id[x],c);x=fa[f1];f1=top[x];}if(dep[x]>dep[y]) swap(x,y);update(1,id[x],id[y],c);
}
void init()
{memset(son,-1,sizeof(son));cnt=0;for(int i=0;i<=n;i++) g[i].clear();
}int main()
{while(~scanf("%d%d",&n,&m)){init();for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}dfs1(1,0,1);dfs2(1,1);build(1,1,n);while(m--){char op[20];scanf("%s",op);if(op[0]=='Q'){int x,y;scanf("%d%d",&x,&y);printf("%d\n",qPath(x,y));}else{int x,y,c;scanf("%d%d%d",&x,&y,&c);cPath(x,y,c);}}}return 0;
}