BZOJ原题地址
洛谷原题地址
思路
树上路径修改，当然是选择树链剖分这种没有思维含量的暴力了啊。。。
颜色段的问题，考虑用线段树来维护。每个节点储存区间的颜色段数以及左右端点的颜色种类。当我们要把两个区间的信息合并的时候，只需要判断一下端点处颜色来决定要不要将颜色段数减一就行了。。。
我的写法的一个问题是，在路径查询的时候，因为我们得到的是一个“人”字形的路径，需要分别储存左边和右边的信息，加上最后在同一条重链上得到的区间信息，一共有三个区间需要合并。
如图，询问$X$到$Y$的路径上的颜色段时，我们先分别将$X$和$Y$移动到了$A$和$B$，同时记录了$X$经过的路径上的信息$lres$，和$Y$经过的路径上的信息$rres$。最后，我们获得了位于同一条重链上的$A$，$B$之间的信息$res$。
由于树链剖分的性质，我们知道区间的左端点深度更小，所以$lres$，$rres$，$res$在上图状态下的左端点分别为$A$，$B$和$B$，所以在合并的时候，需要交换一下$rres$的左右端点信息。
代码实现
// Paint.cpp: 定义控制台应用程序的入口点。
//XG_Zepto, 5/15/2018. All rights reserved.
//#include "stdafx.h"
#include
#include
#include
#include
#include
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((r+l)>>1)
#define NewN(k) Node(1,k,k)
#define maxn 100100
using namespace std;
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
}l[maxn*2];
struct Node{
int num,lco,rco;
Node(int a=0,int b=0,int c=0){
num=a,lco=b,rco=c;
}
}tree[maxn*4];
int head[maxn],cnt,n,m,top[maxn],fa[maxn],id[maxn],col[maxn];
int son[maxn],siz[maxn],dep[maxn],nco[maxn],nid,lazy[maxn*4];
inline void Add(int x,int y){
l[++cnt]=Edge(y,head[x]);
head[x]=cnt;
}
inline void Pre_Work(int u,int f){
dep[u]=dep[f]+1;fa[u]=f;siz[u]=1;
int maxsiz=-1;
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;if (v==f) continue;
Pre_Work(v,u);siz[u]+=siz[v];
if (siz[v]>maxsiz) maxsiz=siz[v],son[u]=v;
}
}
inline void Re_Build(int u,int topf){
id[u]=++nid,nco[nid]=col[u],top[u]=topf;
if (son[u]) Re_Build(son[u],topf);
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;if (v==fa[u]||v==son[u]) continue;
Re_Build(v,v);
}
}
inline void Swap(Node &x){
swap(x.lco,x.rco);
}
inline void Pushup(int p){
if (tree[ls].lco==0){
tree[p]=tree[rs];
return;
}
if (tree[rs].lco==0){
tree[p]=tree[ls];
return;
}
int sum=tree[ls].num+tree[rs].num;
if (tree[ls].rco==tree[rs].lco) sum--;
tree[p]=Node(sum,tree[ls].lco,tree[rs].rco);
}
inline Node Merge(Node x,Node y){
if (x.lco==0) return y;
if (y.lco==0) return x;
int cut=(x.rco==y.lco);
return Node(x.num+y.num-cut,x.lco,y.rco);
}
inline void Set_Up(int l,int r,int p){
if (l==r){tree[p]=Node(1,nco[l],nco[r]);return;}
Set_Up(l,mid,ls);Set_Up(mid+1,r,rs);Pushup(p);
}
inline void Pushdown(int p){
int te=lazy[p];lazy[p]=0;
Node tem=NewN(te);
tree[ls]=tree[rs]=tem;
lazy[ls]=lazy[rs]=te;
}
inline Node Query(int l,int r,int L,int R,int p){
if (l>R||r=L&&r<=R) return tree[p];
if (lazy[p]) Pushdown(p);
return Merge(Query(l,mid,L,R,ls),Query(mid+1,r,L,R,rs));
}
inline void Change(int l,int r,int L,int R,int k,int p){
if (l>R||r=L&&r<=R){
tree[p]=NewN(k);
lazy[p]=k;
return;
}
if (lazy[p]) Pushdown(p);
Change(l,mid,L,R,k,ls);
Change(mid+1,r,L,R,k,rs);
Pushup(p);
}
inline void Path_Query(int x,int y){
Node lres=rres=res=Node(0,0,0);
while(top[x]!=top[y]){
if (dep[top[x]]>dep[top[y]]){
lres=Merge(Query(1,n,id[top[x]],id[x],1),lres);
x=fa[top[x]];
}
else{
rres=Merge(Query(1,n,id[top[y]],id[y],1),rres);
y=fa[top[y]];
}
}
if (dep[x]dep[y]) swap(x,y);
Change(1,n,id[x],id[y],k,1);
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for (int i=1;i<=n;i++) cin>>col[i];
for (int i=1,t1,t2;i<=n-1;i++)
cin>>t1>>t2,Add(t1,t2),Add(t2,t1);
Pre_Work(1,0);Re_Build(1,1);Set_Up(1,n,1);char op;
for (int i=1;i<=m;i++){
cin>>op;
if (op=='Q'){
int t1,t2;cin>>t1>>t2;
Path_Query(t1,t2);
}
else{
int t1,t2,t3;cin>>t1>>t2>>t3;
Path_Change(t1,t2,t3);
}
}
return 0;
}