題目描述
輸入格式：
輸出格式：
對于每個詢問操作，輸出一行答案。
輸入樣例#1：
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
輸出樣例#1：
3
1
2
分析
樹鍊剖分--> 将一棵樹劃分成幾個區間,怎麼算顔色個數呢
線段樹的val表示區間的顔色段數,如何合并??
代碼
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int first[N],next[N*2],to[N*2],tot;
int n,m,ret,a[N];
int size[N],dep[N],top[N];
int son[N],fa[N],id[N],p[N];
struct Node{int l,r,val,cl,cr,tag;}t[N<<2];
int read(){
int cnt=0,f=1;char ch=0;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();
return cnt*f;
}
void add(int x,int y){
next[++tot]=first[x],first[x]=tot,to[tot]=y;
}
void dfs1(int u,int f){
size[u]=1;
int Maxson=-1;
for(int i=first[u];i;i=next[i]){
int t=to[i]; if(t==f) continue;
dep[t]=dep[u]+1,fa[t]=u;
dfs1(t,u); size[u]+=size[t];
if(size[t]>Maxson) Maxson=size[t],son[u]=t;
}
}
void dfs2(int u,int Top){
id[u]=++ret,p[ret]=u,top[u]=Top;
if(son[u])dfs2(son[u],Top);
for(int i=first[u];i;i=next[i]){
int t=to[i];
if(t!=fa[u]&&t!=son[u]) dfs2(t,t);
}
}
void Pushup(int x){
t[x].val=t[x<<1].val+t[x<<1|1].val;
if(t[x<<1].cr==t[x<<1|1].cl) t[x].val--;
t[x].cl=t[x<<1].cl,t[x].cr=t[x<<1|1].cr;
}
void Pushdown(int x){
if(t[x].tag!=-1){
t[x<<1].tag=t[x<<1|1].tag=t[x].tag;
t[x<<1].val=t[x<<1|1].val=1;
t[x<<1].cl=t[x<<1|1].cl=t[x<<1].cr=t[x<<1|1].cr=t[x].tag;
t[x].tag=-1;
}
}
void build(int o,int l,int r){
t[o].l=l,t[o].r=r,t[o].tag=-1;
if(l==r){
t[o].val=1;
t[o].cl=t[o].cr=a[p[l]];
return;
}
int mid=(l+r)>>1;
build(o<<1,l,mid),build(o<<1|1,mid+1,r);
Pushup(o);
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
if(dep[x]<=dep[y]) return x;
else return y;
}
int Color(int o,int x){
Pushdown(o);
if(t[o].l==t[o].r) return t[o].cl;
int mid=(t[o].l+t[o].r)>>1;
if(x<=mid) return Color(o<<1,x);
else return Color(o<<1|1,x);
}
int quary(int o,int L,int R){
if(L<=t[o].l&&t[o].r<=R){
return t[o].val;
}
Pushdown(o);
int mid=(t[o].l+t[o].r)>>1;
int ans=0;
if(L>mid) ans+=quary(o<<1|1,L,R);
else if(R<=mid) ans+=quary(o<<1,L,R);
else{
ans+=quary(o<<1,L,R)+quary(o<<1|1,L,R);
if(t[o<<1].cr==t[o<<1|1].cl) ans--;
}
return ans;
}
int Quary(int x,int y){
int ans=0;
while(top[x]!=top[y]){
ans+=quary(1,id[top[x]],id[x]);
if(Color(1,id[top[x]])==Color(1,id[fa[top[x]]])) ans--;
x=fa[top[x]];
}
ans+=quary(1,id[y],id[x]);
return ans;
}
void update(int o,int L,int R,int val){
if(L<=t[o].l&&t[o].r<=R){
t[o].tag=val,t[o].cl=t[o].cr=val;
t[o].val=1; return;
}
Pushdown(o);
int mid=(t[o].l+t[o].r)>>1;
if(L<=mid) update(o<<1,L,R,val);
if(R>mid) update(o<<1|1,L,R,val);
Pushup(o);
}
void Update(int x,int y,int val){
while(top[x]!=top[y]){
update(1,id[top[x]],id[x],val);
x=fa[top[x]];
}
update(1,id[y],id[x],val);
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<n;i++){
int x=read(),y=read();
add(x,y),add(y,x);
}
dep[1]=1,dfs1(1,0); dfs2(1,1),build(1,1,n);
while(m--){
char ch=getchar();int x=read(),y=read();
if(ch=='Q'){
int l=lca(x,y);
printf("%d\n",Quary(x,l)+Quary(y,l)-1);
}
if(ch=='C'){
int val=read(),l=lca(x,y);
Update(x,l,val),Update(y,l,val);
}
}
return 0;
}