急急急，求完全正确的快读板子！！！
首先这其实是半篇题解。
关于染色这道题。
其实思路非常简单，只要想到树剖，之后用线段树去维护左右边界上的颜色以及区间答案即可。
只需注意pushup的时候要把左右边界颜色更新，转移时相邻区间看颜色相等就答案-1。
正解代码：
#include<bits/stdc++.h>
#define ll long long
#define qr qr()
#define pa pair<int,int>
#define fr first
#define sc second
#define lc tree[rt].ls
#define rc tree[rt].rs
using namespace std;
const int N=2e5+200;
int n,m,num[N],nd_rt[N],dep[N],son[N],nd_tot,cnt,tot,id[N],rk[N],top[N],head[N],fa[N],size[N];
struct node{
int t,nx;
}edge[N];
struct What_can_I_say{
int ls,rs,l,r,sum,cl,cr,lz;
}tree[N<<3];
inline int qr
{
int x=0;char ch=getchar();bool f=0;
while(ch>57||ch<48)
{
if(ch=='-')f=1;
ch=getchar();
}
while(ch<=57&&ch>=48)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
void add(int f,int t)
{
edge[++tot]={t,head[f]};
head[f]=tot;
}
void pushup(int rt)
{
tree[rt].cl=tree[lc].cl,tree[rt].cr=tree[rc].cr;
tree[rt].sum=tree[lc].sum+tree[rc].sum-(tree[lc].cr==tree[rc].cl);
}
void pushdown(int rt)
{
if(tree[rt].lz)
{
tree[lc].lz=tree[rt].lz;
tree[rc].lz=tree[rt].lz;
tree[lc].sum=1,tree[rc].sum=1;
tree[lc].cl=tree[rt].lz,tree[lc].cr=tree[rt].lz;
tree[rc].cl=tree[rt].lz,tree[rc].cr=tree[rt].lz;
tree[rt].lz=0;
}
}
void build(int &rt,int l,int r)
{
rt=++cnt;
tree[rt].l=l;
tree[rt].r=r;
if(l==r)
{
tree[rt].sum=1;
tree[rt].cl=num[id[l]],tree[rt].cr=num[id[l]];
return ;
}
int md=(l+r)/2;
build(lc,l,md);
build(rc,md+1,r);
pushup(rt);
}
void update(int rt,int l,int r,int pos)
{
if(tree[rt].l>=l&&tree[rt].r<=r)
{
tree[rt].sum=1;
tree[rt].lz=pos;
tree[rt].cl=pos,tree[rt].cr=pos;
return ;
}
pushdown(rt);
if(tree[lc].r>=l)update(lc,l,r,pos);
if(tree[lc].r<r)update(rc,l,r,pos);
pushup(rt);
}
int get_sum(int rt,int l,int r)
{
if(tree[rt].l>=l&&tree[rt].r<=r)
{
// printf("(%d,%d)%d %d\n",tree[rt].l,tree[rt].r,tree[rt].cl,tree[rt].cr);
return tree[rt].sum;
}
pushdown(rt);
int ans=0;
if(tree[lc].r>=l)ans+=get_sum(lc,l,r);
if(tree[lc].r<r)ans+=get_sum(rc,l,r)-(ans&&tree[lc].cr==tree[rc].cl);
pushup(rt);
return ans;
}
int check(int rt,int st)
{
if(tree[rt].l==tree[rt].r)
return tree[rt].cl;
pushdown(rt);
if(tree[lc].r>=st)return check(lc,st);
else return check(rc,st);
}
inline int ask(int a,int b)
{
int ans=0,laa=0,lab=0;
while(1)
{
if(dep[top[a]]<dep[top[b]])swap(a,b),swap(laa,lab);
// printf("%d %d %d %d %d %d %d\n",get_sum(nd_rt[top[a]],rk[top[a]],rk[a]),laa,lab,a,b,f,ans);
if(top[a]!=top[b])
{
ans+=get_sum(nd_rt[top[a]],rk[top[a]],rk[a])-(laa==check(nd_rt[top[a]],rk[a]));
laa=tree[nd_rt[top[a]]].cl;
a=fa[top[a]];
}
else
{
if(dep[a]>dep[b])swap(a,b),swap(laa,lab);
ans+=get_sum(nd_rt[top[a]],rk[a],rk[b])-(laa==check(nd_rt[top[a]],rk[a]))-(lab==check(nd_rt[top[a]],rk[b]));
// printf("%d %d %d %d %d %d %d\n",get_sum(nd_rt[top[a]],rk[a],rk[b]),laa,lab,a,b,f,ans);
return ans;
}
}
}
inline void re(int a,int b,int pos)
{
while(1)
{
if(dep[top[a]]<dep[top[b]])swap(a,b);
if(top[a]!=top[b])
{
update(nd_rt[top[a]],rk[top[a]],rk[a],pos);
a=fa[top[a]];
}
else
{
if(dep[a]>dep[b])swap(a,b);
update(nd_rt[top[a]],rk[a],rk[b],pos);
return ;
}
}
}
void get_son(int now)
{
size[now]=1;
for(int i=head[now];i;i=edge[i].nx)
{
int t=edge[i].t;
if(t!=fa[now])
{
dep[t]=dep[now]+1,fa[t]=now;
get_son(t);
if(size[son[now]]<size[t])son[now]=t;
size[now]+=size[t];
}
}
}
void dfs(int now)
{
rk[now]=++nd_tot;
id[nd_tot]=now;
if(!son[now])
{
build(nd_rt[top[now]],rk[top[now]],rk[now]);
return;
}
top[son[now]]=top[now];dfs(son[now]);
for(int i=head[now];i;i=edge[i].nx)
{
int t=edge[i].t;
if(t!=son[now]&&t!=fa[now])
{
top[t]=t;
dfs(t);
}
}
}
void init()
{
// n=qr,m=qr;
scanf("%d%d",&n,&m);
top[1]=1,dep[1]=1;
// for(int i=1;i<=n;++i)num[i]=qr;
for(int i=1;i<=n;++i)scanf("%d",&num[i]);
for(int i=1;i<n;++i)
{
// int a=qr,b=qr;
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
get_son(1);
dfs(1);
// for(int i=1;i<=n;++i)printf("%d ",top[i]);
// putchar('\n');
char op[50];
for(int i=1;i<=m;++i)
{
cin>>op+1;
if(op[1]=='Q')
{
// int a=qr,b=qr;
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",ask(a,b));
}else
{
int a,b,pos;
scanf("%d%d%d",&a,&b,&pos);
re(a,b,pos);
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
init();
return 0;
}
正片后记：
思路清晰地打完代码，然后顺利地爆了零。
改了一天多，最后无处可改了，想着就把快读注释了，再试试。
然后就A了。
所以就有了本篇题解的挠餐题目。
在我得到一个完美的板子前我是不会改标题的尽管这看起来很唐。
所以。