树剖简单题
线段树维护一下区间颜色段数、左右端点颜色
查询的时候看一下两端首尾是否相同就可以了
mlgb线段树标记没清0调了我3
心态崩溃
#include<bits/stdc++.h>
using namespace std;
#define gc getchar
inline int read(){
int res=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while((isdigit(ch)))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return res;
}
const int N=100005;
int n,m,adj[N],nxt[N<<1],to[N<<1],c[N],cnt;
char op[4];
namespace Seg{
#define lc (u<<1)
#define rc ((u<<1)|1)
#define mid ((l+r)>>1)
int tr[N<<2],cov[N<<2],sc[N<<2],dc[N<<2],idx[N<<2];
inline void pushdown(int u){
if(!cov[u])return;
cov[rc]=cov[lc]=sc[lc]=sc[rc]=dc[lc]=dc[rc]=cov[u],tr[lc]=tr[rc]=1,cov[u]=0;
}
inline void pushup(int u){
sc[u]=sc[lc],dc[u]=dc[rc],tr[u]=tr[lc]+tr[rc]+((dc[lc]==sc[rc])?-1:0);
}
void buildtree(int u,int l,int r){
if(l==r){
tr[u]=1,sc[u]=dc[u]=c[idx[l]];return;
}
buildtree(lc,l,mid);
buildtree(rc,mid+1,r);
pushup(u);
}
void update(int u,int l,int r,int st,int des,int clo){
if(st<=l&&r<=des){
tr[u]=1,sc[u]=dc[u]=cov[u]=clo;return;
}
pushdown(u);
if(st<=mid)update(lc,l,mid,st,des,clo);
if(mid<des)update(rc,mid+1,r,st,des,clo);
pushup(u);
}
int find(int u,int l,int r,int pos){
if(l==r)return sc[u];
pushdown(u);int k;
if(pos<=mid)k=find(lc,l,mid,pos);
else k=find(rc,mid+1,r,pos);
pushup(u);return k;
}
int query(int u,int l,int r,int st,int des){
if(st<=l&&r<=des){
return tr[u];
}
pushdown(u);int res=0;
if(st<=mid)res+=query(lc,l,mid,st,des);
if(mid<des)res+=query(rc,mid+1,r,st,des);
pushup(u);
if(st<=mid&&mid<des&&sc[rc]==dc[lc])--res;
return res;
}
}
namespace SLPF{
using namespace Seg;
int pos[N],top[N],fa[N],siz[N],son[N],dep[N],tot;
inline void addedge(int u,int v){
nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
void dfs1(int u){
siz[u]=1;
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
if(v==fa[u])continue;
fa[v]=u,dep[v]=dep[u]+1;
dfs1(v),siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int tp){
pos[u]=++tot,idx[tot]=u,top[u]=tp;
if(!son[u])return;
dfs2(son[u],tp);
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
inline void pathupdate(int u,int v,int clo){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
update(1,1,n,pos[top[u]],pos[u],clo);
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
update(1,1,n,pos[v],pos[u],clo);
}
inline int pathquery(int u,int v){
int res=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
res+=query(1,1,n,pos[top[u]],pos[u]);
if(find(1,1,n,pos[top[u]])==find(1,1,n,pos[fa[top[u]]]))res--;
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
res+=query(1,1,n,pos[v],pos[u]);
return res;
}
}
using namespace SLPF;
inline void init(){
dfs1(1),dfs2(1,1);
buildtree(1,1,n);
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)c[i]=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
addedge(u,v),addedge(v,u);
}
init();
for(int i=1;i<=m;i++){
scanf("%s",op);
if(op[0]=='C'){
int u=read(),v=read(),cl=read();
pathupdate(u,v,cl);
}
else {
int u=read(),v=read();
cout<<pathquery(u,v)<<'
';
}
}
}