Description
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），
如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
Input
第一行包含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）路径上的颜色段数量。
Output
对于每个询问操作，输出一行答案。
Sample Input
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
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
Sample Output
3
1
2
1
2
HINT
数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。
一眼：链剖
两眼：链剖+两个区间相邻处特判
和学长说了一句：感觉不是很难写（flag）
然后我处理的时候是直接当区间修改时用for循环将线段树区间更新
……正确性当然可以保证啦……出乎意料的是并没有T飞……就T了一个点
去隔壁请教了学长被告知要维护线段树的两端颜色……
于是开始了漫长的调试……
其实这个题只要想到了维护两端的值就很好搞了啊……
哪怕像我想不到维护两端也有95可拿对不对【滑稽】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAX (150000+5)
using namespace std;
struct node
{
int down;//下传标记
int sum;//该区间有几种颜色
int l,r;//该区间左右端点的颜色
} Segt[MAX*];
struct node1
{
int to;
int next;
} edge[MAX*];
int Father[MAX],Depth[MAX];
int Sum[MAX],Son[MAX],Top[MAX];
int TREE[MAX],T_NUM[MAX];
int num_edge,head[MAX],n,cnt;
int a[MAX]; inline int get()//神TM快读，维护左右颜色前卡常用的但没卡过去
{
char c;
int x=,f=;
c=getchar();
while (c<''||c>'')
{
if (c=='-') f=-;
c=getchar();
}
while (c>=''&&c<='')
{
x=x*+c-'';
c=getchar();
}
return x*f;
} void add(int u,int v)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
head[u]=num_edge;
} void Build(int node,int l,int r)
{
if (l==r)
{
Segt[node].sum=;
Segt[node].l=Segt[node].r=TREE[l];
}
else
{
int mid=(l+r)/;
Build(node*,l,mid);
Build(node*+,mid+,r);//这里维护好麻烦啊……早知道写个pushup了
Segt[node].l=Segt[node*].l;
Segt[node].r=Segt[node*+].r;
Segt[node].sum=Segt[node*].sum+Segt[node*+].sum-(Segt[node*].r==Segt[node*+].l);
}
} void Pushdown(int node)
{
if (Segt[node].down!=)
{
Segt[node*].sum=;//因为修改成了一个数所以肯定只有一种颜色
Segt[node*+].sum=; Segt[node*].down=Segt[node].down;//down存下传的颜色编号
Segt[node*+].down=Segt[node].down; Segt[node*].l=Segt[node*].r=Segt[node].down;
Segt[node*+].l=Segt[node*+].r=Segt[node].down; Segt[node].down=;
}
} int Query(int node,int l,int r,int l1,int r1)
{
if (r<l1 || l>r1)
return ;
if (l1<=l && r<=r1)
return Segt[node].sum;
Pushdown(node);
int mid=(l+r)/;
int x=Query(node*,l,mid,l1,r1);
int y=Query(node*+,mid+,r,l1,r1);
if (x!= && y!=)
return x+y-(Segt[node*].r==Segt[node*+].l);
return max(x,y);
} void Update(int node,int l,int r,int l1,int r1,int k)//区间更新模板
{
if (r<l1 || l>r1)
return;
if (l1<=l && r<=r1)
{
Segt[node].down=k;
Segt[node].sum=;
Segt[node].l=Segt[node].r=k;
return;
}
Pushdown(node);
int mid=(l+r)/;
Update(node*,l,mid,l1,r1,k);
Update(node*+,mid+,r,l1,r1,k);//再一次后悔没写pushup
Segt[node].l=Segt[node*].l;
Segt[node].r=Segt[node*+].r;
Segt[node].sum=Segt[node*].sum+Segt[node*+].sum-(Segt[node*].r==Segt[node*+].l);
} int Ask(int node,int l,int r,int x)//查询某个点的颜色
{
if (l==r)
return Segt[node].l;
else
{
Pushdown(node);
int mid=(l+r)/;
if (x<=mid) return Ask(node*,l,mid,x);
else return Ask(node*+,mid+,r,x);
}
} int Get(int x,int y)
{
int fx=Top[x],fy=Top[y];
int Ans=;
while (fx!=fy)
{
if (Depth[fx]<Depth[fy])
swap(fx,fy),swap(x,y);
int re=Ask(,,n,T_NUM[fx]);
int fun=Ask(,,n,T_NUM[Father[fx]]);
Ans+=Query(,,n,T_NUM[fx],T_NUM[x])-(re==fun);
x=Father[fx],fx=Top[x];
}
if (Depth[x]<Depth[y])
swap(x,y);
return Ans+=Query(,,n,T_NUM[y],T_NUM[x]);
} void Change(int x,int y,int k)
{
int fx=Top[x],fy=Top[y];
while (fx!=fy)
{
if (Depth[fx]<Depth[fy])
swap(fx,fy),swap(x,y);
Update(,,n,T_NUM[fx],T_NUM[x],k);
x=Father[fx],fx=Top[x];
}
if (Depth[x]<Depth[y])
swap(x,y);
Update(,,n,T_NUM[y],T_NUM[x],k);
} void Dfs1(int x)
{
Depth[x]=Depth[Father[x]]+;
Sum[x]=;
for (int i=head[x]; i!=; i=edge[i].next)
if (edge[i].to!=Father[x])
{
Father[edge[i].to]=x;
Dfs1(edge[i].to);
Sum[x]+=Sum[edge[i].to];
if (Son[x]== || Sum[Son[x]]<Sum[edge[i].to])
Son[x]=edge[i].to;
}
} void Dfs2(int x,int pre)
{
TREE[++cnt]=a[x];
T_NUM[x]=cnt;
Top[x]=pre;
if (Son[x]!=)
Dfs2(Son[x],pre);
for (int i=head[x]; i!=; i=edge[i].next)
if (edge[i].to!=Son[x] && edge[i].to!=Father[x])
Dfs2(edge[i].to,edge[i].to);
} int main()
{
char ch;
int x,y,k,m,u,v;
n=get();
m=get();
for (int i=; i<=n; ++i)
a[i]=get();
for (int i=; i<=n-; ++i)
{
u=get();
v=get();
add(u,v);
add(v,u);
}
Dfs1();
Father[]=;
Dfs2(,);
Build(,,n);
for (int i=; i<=m; ++i)
{
ch=getchar();
while (ch!='C'&&ch!='Q') ch=getchar();
if (ch=='Q')
x=get(),y=get(),printf("%d\n",Get(x,y));
else
x=get(),y=get(),k=get(),Change(x,y,k);
}
}