题目描述
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
输入
第一行包含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）路径上的颜色段数量。
输出
对于每个询问操作，输出一行答案。
样例输入
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
样例输出
3 1 2
提示
N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。
题解
从开始打就感觉这题绝对会白打，果然如此。刚开始学树剖，对题型的了解还很不全面。
1.刚开始接触的 A难存的情缘 和 C货车运输 是边权下放、边权修改、路径查询
if(id[x]<id[y])
res=qd(res,query(id[x]+1,id[y],1,1,n))；
void change(int p,int t,int r,int z,int y)
{
if(z==y)
{
mx[r]=t;
return;
}
int mid=(z+y)/2;
if(p<=mid) change(p,t,r*2,z,mid);
else change(p,t,r*2+1,mid+1,y);
mx[r]=qd(mx[r*2],mx[r*2+1]);
}
2.后来做的 B树上操作 和 E 树的统计 是点权修改、子树修改、路径查询，用到延迟标记和dfs序
if(id[x]<=id[y]) res+=query(id[x],id[y],1,1,n);
void change(int fr,int to,ll a,int r,int z,int y)
{
if(fr<=z&&to>=y)
{
lazy[r]+=a;
t[r].sm+=(long long)(y-z+1)*a;
return;
}
pushdown(r);
int mi=(t[r].le+t[r].ri)>>1;
if(fr<=mi) change(fr,to,a,r<<1,z,mi);
if(to>mi) change(fr,to,a,(r<<1)|1,mi+1,y);
pushup(r);
}
3.一直到今天的考试，我才明白change函数也可以像query一样分层操作。路径修改，路径查询，并且加了方向与合并。特别的是，把链上翻时比较链端和链端的父亲，来确认是否能合并一个色段。
query(id[fa[fx]],id[fa[fx]],1,1,n);
zd2=zd1;
query(id[fx],id[fx],1,1,n);
if(zd1==zd2) res--;
因为有hotel的经验，在线段树里记录左右端颜色并不难想到，延迟标记也是理所当然。其他步骤都比较容易，只有没打过的路径修改和查询合并是问题所在。只要fx和fa[fx]颜色相同，就可以合并一个色块。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int sj=;
int n,m,ys[sj],h[sj],e,a1,a2,a3,zd1,zd2;
char ss;
struct B
{
int u,v,ne;
}b[sj*];
void add(int x,int y)
{
e++;
b[e].ne=h[x];
b[e].u=x;
b[e].v=y;
h[x]=e;
}
void init()
{
scanf("%d%d",&n,&m);
memset(h,-,sizeof(h));
for(int i=;i<=n;i++)
scanf("%d",&ys[i]);
for(int i=;i<n;i++)
{
scanf("%d%d",&a1,&a2);
add(a1,a2);
add(a2,a1);
}
}
int fa[sj]={},son[sj]={},size[sj],dep[sj]={};
void dfs1(int x)
{
size[x]=;
for(int i=h[x];i!=-;i=b[i].ne)
{
int to=b[i].v;
if(to!=fa[x])
{
fa[to]=x;
dep[to]=dep[x]+;
dfs1(to);
size[x]+=size[to];
if(size[to]>size[son[x]]) son[x]=to;
}
}
}
int top[sj],pos[sj],id[sj],cnt,sd[sj];
void dfs2(int x,int y)
{
top[x]=y;
id[x]=++cnt;
sd[id[x]]=x;
pos[cnt]=x;
if(son[x]) dfs2(son[x],y);
for(int i=h[x];i!=-;i=b[i].ne)
{
int to=b[i].v;
if(to!=fa[x]&&to!=son[x])
dfs2(to,to);
}
}
struct Tree
{
int ds,zj,yj,zs,ys;
}t[sj*];
int lazy[sj*];
void build(int x,int z,int y)
{
t[x].zj=z;
t[x].yj=y;
if(z==y)
{
t[x].ds=;
t[x].zs=t[x].ys=ys[pos[z]];
return;
}
int mid=(z+y)>>,ze=x<<,ye=(x<<)|;
build(ze,z,mid);
build(ye,mid+,y);
t[x].ds=t[ze].ds+t[ye].ds;
if(t[ze].ys==t[ye].zs)
t[x].ds--;
t[x].ys=t[ye].ys;
t[x].zs=t[ze].zs;
}
void jh(int &x,int &y)
{
int jy=y;
y=x;
x=jy;
}
void pushdown(int x)
{
if(lazy[x]!=-)
{
int ze=x<<,ye=(x<<)|;
lazy[ze]=lazy[ye]=lazy[x];
t[ze].ds=t[ye].ds=;
t[ze].zs=t[ze].ys=lazy[x];
t[ye].zs=t[ye].ys=lazy[x];
lazy[x]=-;
}
}
void pushup(int x)
{
int ze=x<<,ye=(x<<)|;
t[x].ds=t[ze].ds+t[ye].ds;
if(t[ze].ys==t[ye].zs)
t[x].ds--;
t[x].ys=t[ye].ys;
t[x].zs=t[ze].zs;
}
int query(int s,int to,int r,int z,int y)
{
if(s==z&&to==y)
{
zd1=t[r].zs;
return t[r].ds;
}
pushdown(r);
int mid=(z+y)>>;
int ze=r<<,ye=(r<<)|;
if(to<=mid) return query(s,to,ze,z,mid);
if(s>mid) return query(s,to,ye,mid+,y);
int res=query(s,mid,ze,z,mid)+query(mid+,to,ye,mid+,y);
if(t[ze].ys==t[ye].zs) res--;
return res;
}
int Q(int x,int y)
{
int res=,fx=top[x],fy=top[y];
while(fx^fy)
{
if(dep[fx]<dep[fy])
{
jh(x,y);
jh(fx,fy);
}
res+=query(id[fx],id[x],,,n);
query(id[fa[fx]],id[fa[fx]],,,n);
zd2=zd1;
query(id[fx],id[fx],,,n);
if(zd1==zd2) res--;
x=fa[fx];
fx=top[x];
}
if(dep[x]>dep[y]) jh(x,y);
if(id[x]<=id[y]) res+=query(id[x],id[y],,,n);
return res;
}
void c(int s,int to,int a,int r,int z,int y)
{
if(s==z&&to==y)
{
lazy[r]=a;
t[r].ds=;
t[r].ys=t[r].zs=a;
return;
}
pushdown(r);
int mid=(z+y)>>;
int ze=r<<,ye=(r<<)|;
if(to<=mid) c(s,to,a,ze,z,mid);
if(s>mid) c(s,to,a,ye,mid+,y);
if(to>mid&&s<=mid)
{
c(s,mid,a,ze,z,mid);
c(mid+,to,a,ye,mid+,y);
}
pushup(r);
}
void C(int x,int y,int a)
{
int fx=top[x],fy=top[y];
while(fx^fy)
{
if(dep[fx]<dep[fy])
{
jh(x,y);
jh(fx,fy);
}
c(id[fx],id[x],a,,,n);
x=fa[fx];
fx=top[x];
}
if(dep[x]>dep[y]) jh(x,y);
if(id[x]<=id[y]) c(id[x],id[y],a,,,n);
}
void cl()
{
for(int i=;i<=m;i++)
{
scanf("%s",&ss);
scanf("%d%d",&a1,&a2);
if(ss=='Q')
printf("%d\n",Q(a1,a2));
if(ss=='C')
{
scanf("%d",&a3);
C(a1,a2,a3);
}
}
}
int main()
{
//freopen("t3.txt","r",stdin);
init();
dfs1();
dfs2(,);
memset(lazy,-,sizeof(lazy));
build(,,n);
cl();
//while(1);
return ;
}