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
HINT
数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。
My Solution
一道可爱的树链剖分题啊
注意区间合并和树剖中的calc即可
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; inline int read(){
char ch;
int re=;
bool flag=;
while((ch=getchar())!='-'&&(ch<''||ch>''));
ch=='-'?flag=:re=ch-'';
while((ch=getchar())>=''&&ch<='') re=re*+ch-'';
return flag?-re:re;
} inline char rea(){
char ch;
while((ch=getchar())!='Q'&&ch!='C');
return ch;
} struct edge{
int to,next;
edge(int to=,int next=):
to(to),next(next){}
}; struct segment{
int l,r,lc,rc,sum,tag;
}; const int maxn=1e5+; edge edges[maxn<<];
segment tre[maxn<<];
int n,m,cnt=,root;
//si1,si2表示query操作中取到的最高和最低颜色
int si1,si2,LL,RR;
int head[maxn],data[maxn];
int siz[maxn],fat[maxn],son[maxn],dep[maxn],id[maxn],id_[maxn],top[maxn]; inline void add_edge(int from,int to){
edges[++cnt]=edge(to,head[from]); head[from]=cnt;
edges[++cnt]=edge(from,head[to]); head[to]=cnt;
} void init(){
n=read(); m=read();
for(int i=;i<=n;i++) data[i]=read();
int from,to; cnt=;
for(int i=;i<n;i++){
from=read(); to=read();
add_edge(from,to);
}
} void dfs_1(int x,int fa){
siz[x]=;
dep[x]=dep[fa]+;
fat[x]=fa;
for(int ee=head[x];ee;ee=edges[ee].next)
if(edges[ee].to!=fa){
dfs_1(edges[ee].to,x);
siz[x]+=siz[edges[ee].to];
if(!son[x]||siz[edges[ee].to]>siz[son[x]]) son[x]=edges[ee].to;
}
} void dfs_2(int x,int first){
top[x]=first;
id[x]=++cnt;
id_[cnt]=x;
if(!son[x]) return;
dfs_2(son[x],first);
for(int ee=head[x];ee;ee=edges[ee].next)
if(edges[ee].to!=fat[x]&&edges[ee].to!=son[x]) dfs_2(edges[ee].to,edges[ee].to);
} void push_up(int x){
int lson=x<<,rson=lson|;
tre[x].lc=tre[lson].lc;
tre[x].rc=tre[rson].rc;
tre[x].sum=tre[lson].sum+tre[rson].sum-(tre[lson].rc==tre[rson].lc?:);
} void build(int x,int l,int r){
tre[x].l=l; tre[x].r=r;
if(l==r){
tre[x].lc=tre[x].rc=data[id_[l]];
tre[x].sum=;
return;
}
int mid=(l+r)>>;
build(x<<,l,mid); build(x<<|,mid+,r);
push_up(x);
} void push_down(int x){
int lson=x<<,rson=lson|;
int &c=tre[x].tag;
tre[lson].tag=tre[rson].tag=tre[lson].lc=
tre[lson].rc=tre[rson].lc=tre[rson].rc=c;
tre[lson].sum=; tre[rson].sum=;
c=;
} void make(){
root=; dfs_1(root,);
cnt=; dfs_2(root,root);
build(,,n);
} void update(int x,int L,int R,int c){
if(L<=tre[x].l&&tre[x].r<=R){
tre[x].lc=tre[x].rc=tre[x].tag=c;
tre[x].sum=;
return;
} if(tre[x].tag) push_down(x); int mid=(tre[x].l+tre[x].r)>>;
if(R<=mid) update(x<<,L,R,c);
else if(L>mid) update(x<<|,L,R,c);
else{
update(x<<,L,mid,c);
update(x<<|,mid+,R,c);
}
push_up(x);
} int query_sum(int x,int L,int R){
if(tre[x].l==LL) si1=tre[x].lc;
if(tre[x].r==RR) si2=tre[x].rc;
if(L<=tre[x].l&&tre[x].r<=R) return tre[x].sum; if(tre[x].tag) push_down(x); int mid=(tre[x].l+tre[x].r)>>;
if(R<=mid) return query_sum(x<<,L,R);
if(L>mid) return query_sum(x<<|,L,R);
return query_sum(x<<,L,mid)+query_sum(x<<|,mid+,R)-(tre[x<<].rc==tre[x<<|].lc?:);
} void calc(int ss,int tt,int c){
int f1=top[ss],f2=top[tt];
while(f1!=f2){
if(dep[f1]<dep[f2]){ swap(f1,f2); swap(ss,tt); }
update(,id[f1],id[ss],c);
ss=fat[f1]; f1=top[ss];
}
if(dep[ss]<dep[tt]) swap(ss,tt);
update(,id[tt],id[ss],c);
} int calc(int ss,int tt){
int f1=top[ss],f2=top[tt],ans=;
int sid1=,sid2=;
while(f1!=f2){
if(dep[f1]<dep[f2]){ swap(f1,f2); swap(ss,tt); swap(sid1,sid2); }
LL=id[f1]; RR=id[ss];
ans+=query_sum(,id[f1],id[ss]);
if(si2==sid1) ans--;
sid1=si1; ss=fat[f1]; f1=top[ss];
}
if(dep[ss]<dep[tt]) { swap(ss,tt); swap(sid1,sid2); }
LL=id[tt]; RR=id[ss];
ans+=query_sum(,id[tt],id[ss]);
if(sid1==si2) ans--;
if(sid2==si1) ans--;
return ans;
} void solve(){
char opt;
int ss,tt,c;
for(int i=;i<m;i++){
opt=rea();
switch(opt){
case 'C':{
ss=read(); tt=read(); c=read();
calc(ss,tt,c);
break;
}
case 'Q':{
ss=read(); tt=read();
printf("%d\n",calc(ss,tt));
break;
}
}
}
} int main(){
//freopen("data.in","r",stdin);
init();
make();
solve();
return ;
}
それまでは 閉じこもって
あなたも卵の中なのね