[SDOI2011] 染色

這道題，顯然我們需要樹剖一下

然後我們考慮怎麼用線段樹去維護區間顔色段數

我們會想到我們需要維護這麼幾個東西

1.區間段數

2.區間左端點的顔色

3.區間右端點的顔色

合并的時候就是左兒子的段數加上右兒子的段數，如果左兒子的右端點和右兒子的左端點是一個顔色，那麼就段數-1

因為是區間修改，是以加上一個懶标記就可以了

更新跟普通樹剖一樣，但是查詢不太一樣

這裡提供一種适用範圍更廣的做法

我是受到了這道題的啟發，那道題是求樹上最大子段和，需要維護的東西比較多，是以單純用變量不太好做。

是以我讓我們的 q u e r y query query函數傳回的是一個結構體來儲存這一段的答案的段數，左端點，右端點分别是什麼，然後我們再寫一個 m e r g e merge merge函數來合并兩個結構體，其實寫起來和 p u s h u p pushup pushup差不多，大概是這個樣子的

segment_tree merge(segment_tree l,segment_tree r){
	if(!l.sum)return r;
	if(!r.sum)return l;
	segment_tree res;
	res.lcol=l.lcol,res.rcol=r.rcol;
	res.sum=l.sum+r.sum;
	if(l.rcol==r.lcol)res.sum--;
	return res;	
}
           

那麼我們樹剖查詢的時候，開兩個 s e g m e n t _ t r e e segment\_tree segment_tree類型的結構體變量l，r，分别表示x往上跳到他們的lca的這一段的顔色段數和y跳到 l c a lca lca這一段的顔色段數

然後依次合并就可以了

但是注意一點， m e r g e merge merge函數是不滿足交換律的，是以我們要把 t o p [ x ] − x top[x]-x top[x]−x這一段放在左邊。

最後合并的時候要把l的左端點顔色和右端點顔色交換一下，因為我們要把一個區間整體反轉才能接到一起（可以畫個圖了解一下）

然後如果你隻過了hack資料的話就查一下你的查詢那一段有沒有查反就好了

c o d e   t i m e code \ time code time:

# include <bits/stdc++.h>
using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
const int N=1e5+5;
template <typename T> void read(T &x){
	x=0;int f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
	x*=f;
}

int n,m;
int head[N],cnt;
int a[N],_a[N];
int faz[N],son[N],dep[N],siz[N],top[N],dfn[N],tot;

struct Edge{
	int to,next;	
}e[N<<1];

void add(int x,int y){
	e[++cnt]=(Edge){y,head[x]},head[x]=cnt;	
}

struct segment_tree{
	int l,r;
	int lcol,rcol,sum;	
	int tag;
	segment_tree(){l=r=lcol=rcol=sum=tag=0;}
}seg[N<<2];

# define lc (u<<1)
# define rc (u<<1|1)

void pushup(int u){
	seg[u].sum=seg[lc].sum+seg[rc].sum;
	if(seg[lc].rcol==seg[rc].lcol)seg[u].sum--;
	seg[u].lcol=seg[lc].lcol;
	seg[u].rcol=seg[rc].rcol;	
}

void pushdown(int u){
	seg[lc].sum=1;
	seg[lc].lcol=seg[lc].rcol=seg[u].tag;
	seg[lc].tag=seg[u].tag;
	seg[rc].sum=1;
	seg[rc].lcol=seg[rc].rcol=seg[u].tag;
	seg[rc].tag=seg[u].tag;
	seg[u].tag=0;	
}

segment_tree merge(segment_tree l,segment_tree r){
	if(!l.sum)return r;
	if(!r.sum)return l;
	segment_tree res;
	res.lcol=l.lcol,res.rcol=r.rcol;
	res.sum=l.sum+r.sum;
	if(l.rcol==r.lcol)res.sum--;
	return res;	
}

void build(int u,int l,int r){
	seg[u].l=l,seg[u].r=r;
	if(l==r){seg[u].sum=1,seg[u].lcol=seg[u].rcol=_a[l];return;}
	int mid=l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(u);
}

void update(int u,int l,int r,int k){
	if(seg[u].l>=l&&seg[u].r<=r){
		seg[u].sum=1;
		seg[u].lcol=seg[u].rcol=k;
		seg[u].tag=k;
		return;
	}	
	if(seg[u].tag)pushdown(u);
	int mid=seg[u].l+seg[u].r>>1;
	if(l<=mid)update(lc,l,r,k);
	if(r>mid)update(rc,l,r,k);
	pushup(u);
}

segment_tree query(int u,int l,int r){
	if(seg[u].l>=l&&seg[u].r<=r)return seg[u];
	if(seg[u].tag)pushdown(u);
	int mid=seg[u].l+seg[u].r>>1;
	if(r<=mid)return query(lc,l,r);
	if(l>mid)return query(rc,l,r);
	return merge(query(lc,l,r),query(rc,l,r));	
}

void RouteModify(int x,int y,int k){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		update(1,dfn[top[x]],dfn[x],k);
		x=faz[top[x]];	
	}
	if(dep[x]>dep[y])swap(x,y);
	update(1,dfn[x],dfn[y],k);
}

int RouteQuery(int x,int y){
	segment_tree l,r;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]){
			r=merge(query(1,dfn[top[y]],dfn[y]),r);
			y=faz[top[y]];	
		}
		else{
			l=merge(query(1,dfn[top[x]],dfn[x]),l);
			x=faz[top[x]];	
		}
	}
	if(dep[x]<dep[y])r=merge(query(1,dfn[x],dfn[y]),r);
	else l=merge(query(1,dfn[y],dfn[x]),l);
	swap(l.lcol,l.rcol);
	return merge(l,r).sum; 
}

void dfs1(int u,int fa){
	faz[u]=fa;
	siz[u]=1;
	dep[u]=dep[fa]+1;
	RepG(i,u){
		int v=e[i].to;
		if(v==fa)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}

void dfs2(int u,int _top){
	top[u]=_top;
	dfn[u]=++tot;
	_a[tot]=a[u];
	if(!son[u])return;
	dfs2(son[u],_top);
	RepG(i,u){
		int v=e[i].to;
		if(v==faz[u]||v==son[u])continue;
		dfs2(v,v);
	}
}

int main()
{
	memset(head,-1,sizeof(head));
	read(n),read(m);
	Rep(i,1,n)read(a[i]);
	Rep(i,1,n-1){
		int x,y;
		read(x),read(y);
		add(x,y),add(y,x);
	}
	dfs1(1,0),dfs2(1,1);
	build(1,1,n);
	Rep(i,1,m){
		char opt[10];
		int x,y,z;
		scanf("%s",opt);
		if(opt[0]=='C'){
			read(x),read(y),read(z);
			RouteModify(x,y,z);
		}
		else{
			read(x),read(y);
			printf("%d\n",RouteQuery(x,y));	
		}
	}
	return 0;
}