BZOJ 2243染色木鎖断分

木を与えて、木の上の各点は1つの色があります
2つのアクションを指定
Q:問い合わせノードxからノードyへのパス上の色セグメント数(連続して同じ色が同じセグメントとみなされる)、例えば「112212」は、「11」、「222」、「1」の3セグメントからなる.
C:ノードxからノードyパス上の全ての点を色zに染める
まずこの問題は一見して木の鎖の断分であることがわかる.
そして線分ツリーの区間マージの問題です
各ノードは、区間内のカラーセグメント数、左端のカラー、右端のカラーを保存します.
2区間を併合する場合、左区間右端点と右区間左端点の色が同じであれば、新区間段数は左右区間の和-1となる
そうでなければ両区間の和となる
質問するときもその対処法ですが、左右が逆にならないように気をつけてください
もともとすぐに书き终わってからCとQを読み込んだ时Linuxの中の帰りを忘れてしまったのは'r'これくらいP事WAだったので午后三千组のデータを撮って全部渡して最初の点でWA私を絞めて行きました...
とにかくコードを貼る

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ls tree[p].lson
#define rs tree[p].rson
#define M 100100
using namespace std;
struct Col{	int num,lcol,rcol; }empty;
struct Tree{
	Col col,mark;
	int lson,rson;
}tree[M<<1];
struct abcd{
	int to,next;
}table[M<<1];
int head[M],tot=1;
int n,m,fa[M],col[M],son[M],dpt[M],siz[M],pos[M],top[M],poscol[M],cnt;
void add(int x,int y)
{
	table[++tot].to=y;
	table[tot].next=head[x];
	head[x]=tot;
}
void dfs1(int x)
{
	int i;
	siz[x]=1;
	dpt[x]=dpt[fa[x]]+1;
	for(i=head[x];i;i=table[i].next)
	{
		if(table[i].to==fa[x])
			continue;
		fa[table[i].to]=x;
		dfs1(table[i].to);
		if(siz[table[i].to]>siz[son[x]])
			son[x]=table[i].to;
		siz[x]+=siz[table[i].to];
	}
}
void dfs2(int x)
{
	int i;
	if(son[fa[x]]==x)
		top[x]=top[fa[x]];
	else
	{
		top[x]=x;
		for(i=x;i;i=son[i])
			pos[i]=++cnt;
	}
	poscol[pos[x]]=col[x];
	for(i=head[x];i;i=table[i].next)
	{
		if(table[i].to==fa[x])
			continue;
		dfs2(table[i].to);
	}
}
Col operator + (Col x,Col y)
{
	Col re;
	re.lcol=x.lcol;
	re.rcol=y.rcol;
	re.num=x.num+y.num-(x.rcol==y.lcol);
	return re;
}
void Build_tree(int p,int x,int y)
{
	int mid=x+y>>1;
	if(x==y)
	{
		tree[p].col.num=1;
		tree[p].col.lcol=tree[p].col.rcol=poscol[mid];
		return ;
	}
	ls=++tot;rs=++tot;
	Build_tree(ls,x,mid);
	Build_tree(rs,mid+1,y);
	tree[p].col=tree[ls].col+tree[rs].col;
}
Col getans(int p,int x,int y,int l,int r)
{
	int mid=x+y>>1;
	if(x==l&&y==r)
		return tree[p].col;
	if(tree[p].mark.num)
	{
		tree[ls].col=tree[rs].col=tree[p].mark;
		tree[ls].mark=tree[rs].mark=tree[p].mark;
		tree[p].mark=empty;
	}
	if(r<=mid)	return getans(ls,x,mid,l,r);
	if(l>mid) return getans(rs,mid+1,y,l,r);
	return getans(ls,x,mid,l,mid) + getans(rs,mid+1,y,mid+1,r);
}
int Q(int x,int y)
{
	Col xcol=empty,ycol=empty;
	int fx=top[x],fy=top[y];
	while(fx!=fy)
	{
		if(dpt[fx]<dpt[fy])
			swap(x,y),swap(fx,fy),swap(xcol,ycol);
		xcol=getans(0,1,n,pos[fx],pos[x])+xcol;
		x=fa[fx];
		fx=top[x];
	}
	if(dpt[x]<dpt[y])
		swap(x,y),swap(fx,fy),swap(xcol,ycol);
	xcol=getans(0,1,n,pos[y],pos[x])+xcol;
	return xcol.num+ycol.num-(xcol.lcol==ycol.lcol);
}
void change(int p,int x,int y,int l,int r,Col z)
{
	int mid=x+y>>1;
	if(x==l&&y==r)
	{
		tree[p].col=z;
		tree[p].mark=z;
		return ;
	}
	if(tree[p].mark.num)
	{
		tree[ls].col=tree[rs].col=tree[p].mark;
		tree[ls].mark=tree[rs].mark=tree[p].mark;
		tree[p].mark=empty;
	}
	if(r<=mid)	change(ls,x,mid,l,r,z);
	else if(l>mid) change(rs,mid+1,y,l,r,z);
	else change(ls,x,mid,l,mid,z) , change(rs,mid+1,y,mid+1,r,z);
	tree[p].col=tree[ls].col+tree[rs].col;
}
void C(int x,int y,int z)
{
	int fx=top[x],fy=top[y];
	Col zmark;
	zmark.num=1;
	zmark.lcol=zmark.rcol=z;
	while(fx!=fy)
	{
		if(dpt[fx]<dpt[fy])
			swap(x,y),swap(fx,fy);
		change(0,1,n,pos[fx],pos[x],zmark);
		x=fa[fx];
		fx=top[x];
	}
	if(dpt[x]<dpt[y])
		swap(x,y),swap(fx,fy);
	change(0,1,n,pos[y],pos[x],zmark);
}
inline char get_char()
{
	char c;
	do c=getchar(); while(c=='
'||c==' '||c=='\r');
	return c; 
}
int main()
{
	int i,x,y,z;
	char p;
	
	cin>>n>>m;
	for(i=1;i<=n;i++)
		scanf("%d",&col[i]),col[i]++;
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	tot=0;
	dfs1(1);
	dfs2(1);
	Build_tree(0,1,n);
	for(i=1;i<=m;i++)
	{
		p=get_char();
		if(p=='Q')
		{
			scanf("%d%d",&x,&y);
			printf("%d
",Q(x,y));
		}
		else
		{
			scanf("%d%d%d",&x,&y,&z);
			C(x,y,z+1);
		}
	}
}