考试一共四个半小时，光这道题就打了三个小时。。然后又改了俩小时才过。我太蒟蒻了。
其实数据结构这种题就看第一遍打没打顺，顺了就A了，要是再找错再改就慢了，而且样例过了不能说明任何问题（虽然考试的时候我连样例都没出hhh）
给树按上三个新域，一个是左边的颜色，一个是右边的颜色，一个是颜色段数。
void pushup(int root)
{
tree[root].lcol=tree[root<<1].lcol;
tree[root].rcol=tree[root<<1|1].rcol;
if(tree[root<<1].rcol==tree[root<<1|1].lcol)
tree[root].duan=tree[root<<1].duan+tree[root<<1|1].duan-1;
else
tree[root].duan=tree[root<<1].duan+tree[root<<1|1].duan;
}
这段pushup想必大家就明白怎么递归了。
注意在往上爬的过程当中，一段一段中间的连接区域可能会有颜色相同，需要判断一下，找出fx。
完整代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 500000
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
int n,m;
int v[N];
struct haha
{
int next,to;
}edge[N];
int head[N],cnt=1;
struct qian
{
int left,right;
int lcol,rcol,duan;
}tree[N];
int duan[N];
void add(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int rt[N];
int size[N],son[N],dep[N],fa[N];
void dfs1(int x)
{
size[x]=1;son[x]=0;
for(int i=head[x];i;i=edge[i].next)
{
int to=edge[i].to;
if(to!=fa[x])
{
fa[to]=x;
dep[to]=dep[x]+1;
dfs1(to);
size[x]+=size[to];
if(size[to]>size[son[x]])
son[x]=to;
}
}
}
int id[N],pos[N],top[N];
int ji;
void dfs2(int x,int tp)
{
top[x]=tp;
id[x]=++ji;
pos[ji]=x;
if(son[x])
dfs2(son[x],tp);
for(int i=head[x];i;i=edge[i].next)
{
int to=edge[i].to;
if(to!=fa[x]&&to!=son[x])
dfs2(to,to);
}
}
void pushup(int root)
{
tree[root].lcol=tree[root<<1].lcol;
tree[root].rcol=tree[root<<1|1].rcol;
if(tree[root<<1].rcol==tree[root<<1|1].lcol)
tree[root].duan=tree[root<<1].duan+tree[root<<1|1].duan-1;
else
tree[root].duan=tree[root<<1].duan+tree[root<<1|1].duan;
}
void build(int left,int right,int root)
{
rt[root]=-1;
tree[root].left=left;
tree[root].right=right;
if(left==right)
{
tree[root].lcol=tree[root].rcol=v[pos[left]];
tree[root].duan=1;
return;
}
int mid=(left+right)>>1;
build(left,mid,root<<1);
build(mid+1,right,root<<1|1);
pushup(root);
}
void pushdown(int root)
{
if(rt[root]>=0)
{
rt[root<<1]=rt[root];
rt[root<<1|1]=rt[root];
tree[root<<1].lcol=tree[root<<1].rcol=rt[root];
tree[root<<1|1].lcol=tree[root<<1|1].rcol=rt[root];
tree[root<<1].duan=tree[root<<1|1].duan=1;
rt[root]=-1;
}
}
void change(int left,int right,int num,int root)
{
if(left<=tree[root].left&&right>=tree[root].right)
{
rt[root]=num;
tree[root].lcol=tree[root].rcol=num;
tree[root].duan=1;
return;
}
pushdown(root);
int mid=(tree[root].right+tree[root].left)>>1;
if(left<=mid)
change(left,right,num,root<<1);
if(right>mid)
change(left,right,num,root<<1|1);
pushup(root);
}
int query(int left,int right,int root)
{
if(left<=tree[root].left&&right>=tree[root].right)
return tree[root].duan;
pushdown(root);
int mid=(tree[root].left+tree[root].right)>>1;
if(right<=mid)
return query(left,right,root<<1);
else
if(left>mid)
return query(left,right,root<<1|1);
else
{
int tmp=1;
if(tree[root<<1].rcol!=tree[root<<1|1].lcol)
tmp=0;
return query(left,mid,root<<1)+query(mid+1,right,root<<1|1)-tmp;
}
}
int temp1,temp2;
void check(int po,int root)
{
pushdown(root);
if(tree[root].left==tree[root].right)
{
temp1=tree[root].lcol;
return;
}
int mid=(tree[root].right+tree[root].left)>>1;
if(po<=mid)
check(po,root<<1);
else
check(po,root<<1|1);
}
void check2(int po,int root)
{
pushdown(root);
if(tree[root].left==tree[root].right)
{
temp2=tree[root].lcol;
return;
}
int mid=(tree[root].right+tree[root].left)>>1;
if(po<=mid)
check2(po,root<<1);
else
check2(po,root<<1|1);
}
int erx,fux,ery,fuy;
int Query(int x,int y)
{
int fx=top[x],fy=top[y];
int ans=0;
while(fx!=fy)
{
if(dep[fx]>dep[fy])
{
check(id[fa[fx]],1);
check2(id[fx],1);
ans+=query(id[fx],id[x],1);
if(temp1==temp2)
ans--;
x=fa[fx];
fux=x;
erx=fx;
fx=top[x];
}
else
{
check(id[fa[fy]],1);
check2(id[fy],1);
ans+=query(id[fy],id[y],1);
if(temp1==temp2)
ans--;
y=fa[fy];
fuy=y;
ery=fy;
fy=top[y];
}
}
if(dep[x]>dep[y])
{
//check(id[erx],1);
//check(id[fux],1);
ans+=query(id[y],id[x],1);
//if(temp1==temp2)
//ans--;
}
else
{
//check(id[ery],1);
//check(id[fuy],1);
ans+=query(id[x],id[y],1);
//if(temp1==temp2)
//ans--;
}
return ans;
}
void Change(int x,int y,int z)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])
{
swap(fx,fy);
swap(x,y);
}
change(id[fx],id[x],z,1);
x=fa[fx];fx=top[x];
}
if(dep[x]>dep[y])
swap(x,y);
change(id[x],id[y],z,1);
}
int read()
{
int su=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch<='9'&&ch>='0')
{
su=su*10+ch-'0';
ch=getchar();
}
return su;
}
int main()
{
//freopen("paint6.in","r",stdin);
//freopen("paint66.out","w",stdout);
scanf("%d%d",&n,&m);
pos(i,1,n)
v[i]=read();
pos(i,1,n-1)
{
int x,y;
x=read();y=read();
add(x,y);
add(y,x);
}
dfs1(1);
dfs2(1,1);
build(1,n,1);
pos(i,1,m)
{
char p;
int x,y,z;
scanf("%s",&p);
if(p=='C')
{
x=read();y=read();z=read();
Change(x,y,z);
}
if(p=='Q')
{
x=read();y=read();
printf("%d\n",Query(x,y));
}
}
//while(1);
return 0;
}