[文章目录]
Description
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。n<=100000,m<=100000
树链剖分+线段树染色问题。第二次写树链剖分。
树链剖分，感觉还是dfs的时候少传参比较好吧。于是吧pre改成了fa[]。
线段树还是写结构体里比较清真吧。维护四个参数。
left[]-左端点颜色，right[]-右端点颜色，num[]区间颜色段数量，lazy[]染色延迟标记。建树的时候直接就将点的颜色赋给lazy就好了吧。
然后就是码力和思想缜密的问题了。感觉还行吧。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 101000
int n,m,val[N];
char st[10];
int head[N],to[N<<1],nxt[N<<1],cnt;
void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int fa[N],deep[N],siz[N],son[N];
void dfs1(int x)
{
int k=-1<<30;siz[x]++;
for(int y,i=head[x];i;i=nxt[i])
{
y=to[i];
if(y!=fa[x])
{
fa[y]=x;deep[y]=deep[x]+1;
dfs1(y);
siz[x]+=siz[y];
if(siz[y]>k) k=siz[y],son[x]=y;
}
}
}
int tre[N],tid[N],top[N],tot;
void dfs2(int x,int anc)
{
tre[++tot]=val[x];tid[x]=tot;top[x]=anc;
if(son[x]) dfs2(son[x],anc);
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa[x]&&to[i]!=son[x])
dfs2(to[i],to[i]);
}
struct seg
{
int num[N<<2],lazy[N<<2],left[N<<2],right[N<<2];
seg(){memset(lazy,-1,sizeof(lazy));}
void pushup(int pos)
{
left[pos]=left[pos<<1];right[pos]=right[pos<<1|1];
num[pos]=num[pos<<1]+num[pos<<1|1];
if(right[pos<<1]==left[pos<<1|1]) num[pos]--;
}
void pushdown(int pos)
{
if(lazy[pos]!=-1)
{
if(num[pos<<1]) {left[pos<<1]=right[pos<<1]=lazy[pos<<1]=lazy[pos];num[pos<<1]=1;}
if(num[pos<<1|1]) {left[pos<<1|1]=right[pos<<1|1]=lazy[pos<<1|1]=lazy[pos];num[pos<<1|1]=1;}
lazy[pos]=-1;
}
}
void build(int pos,int l,int r)
{
if(l==r){left[pos]=right[pos]=lazy[pos]=tre[r];num[pos]=1;return ;}
int mid=l+r>>1;
build(pos<<1,l,mid);build(pos<<1|1,mid+1,r);
pushup(pos);
}
int query_pos(int pos,int l,int r,int x)
{
if(lazy[pos]!=-1) return lazy[pos];
int mid=l+r>>1;
if(x<=mid) return query_pos(pos<<1,l,mid,x);
else return query_pos(pos<<1|1,mid+1,r,x);
}
int query(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return num[pos];
int mid=l+r>>1;pushdown(pos);
if(y<=mid) return query(pos<<1,l,mid,x,y);
if(x>mid) return query(pos<<1|1,mid+1,r,x,y);
if(right[pos<<1]==left[pos<<1|1])
return query(pos<<1,l,mid,x,y)+query(pos<<1|1,mid+1,r,x,y)-1;
else return query(pos<<1,l,mid,x,y)+query(pos<<1|1,mid+1,r,x,y);
}
void fix(int pos,int l,int r,int x,int y,int col)
{
if(x<=l&&y>=r) {left[pos]=right[pos]=lazy[pos]=col;num[pos]=1; return ; }
int mid=l+r>>1; pushdown(pos);
if(y<=mid) fix(pos<<1,l,mid,x,y,col);
else if(x>mid) fix(pos<<1|1,mid+1,r,x,y,col);
else fix(pos<<1,l,mid,x,y,col),fix(pos<<1|1,mid+1,r,x,y,col);
pushup(pos);
}
}T1;
void Fix()
{
int x,y,c; scanf("%d%d%d",&x,&y,&c);
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
T1.fix(1,1,n,tid[top[x]],tid[x],c);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
T1.fix(1,1,n,tid[x],tid[y],c);
}
void Query()
{
int c[2],flag,col[2],re=0;
col[0]=col[1]=-1;
scanf("%d%d",&c[0],&c[1]);
while(top[c[0]]!=top[c[1]])
{
if(deep[top[c[0]]]<deep[top[c[1]]]) flag=1;
else flag=0;
re+=T1.query(1,1,n,tid[top[c[flag]]],tid[c[flag]]);
if(T1.query_pos(1,1,n,tid[c[flag]])==col[flag]) re--;
col[flag]=T1.query_pos(1,1,n,tid[top[c[flag]]]);
c[flag]=fa[top[c[flag]]];//第一次写成c[flag]=fa[c[flag]],WA-1
}
if(deep[c[0]]>deep[c[1]]) swap(c[0],c[1]),swap(col[0],col[1]);//第二次没交换col[]，WA-2
re+=T1.query(1,1,n,tid[c[0]],tid[c[1]]);
re-=(T1.query_pos(1,1,n,tid[c[0]])==col[0])+(T1.query_pos(1,1,n,tid[c[1]])==col[1]);
printf("%d\n",re);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&val[i]);
for(int x,y,i=1;i<n;i++) {scanf("%d%d",&x,&y); add(x,y); add(y,x); }
deep[1]=1;dfs1(1);dfs2(1,1); T1.build(1,1,n);
while(m--)
{
scanf("%s",st);
switch(st[0])
{
case 'C':Fix();break;
case 'Q':Query();break;
}
}
return 0;
}