#include <bits/stdc++.h>
#define N 101000
#define FREI freopen("in.txt","r",stdin)
#define FREO freopen("out.txt","w",stdout)
#define Mem(a,b) memset(a,b,sizeof(a))
#define lson root<<1
#define rson root<<1|1
#define Mid int mid=(l+r)>>1
#define inf 0x3f3f3f3f
using namespace std;
int n,m,k,siz[N],fa[N],son[N],cnt,f[N],invf[N],dep[N],tp[N],ecnt,ans,res,rr;
int node[N];
struct edge {
int v,next;
};
edge e[N<<2];
int head[N],mark[N<<2];
struct tree {
int l,r,cnt;
};
tree seg[N<<2];
void add(int u,int v) {
e[ecnt]=(edge) {
v,head[u]
};
head[u]=ecnt++;
}
void initsplit(){
Mem(head,-1);
dep[1]=0;
Mem(son,-1);
Mem(mark,-1);
ecnt=cnt=0;
}
void dfs1(int u,int father) {
dep[u]=dep[father]+1;
fa[u]=father;
siz[u]=1;
for(int i=head[u]; ~i; i=e[i].next) {
int v=e[i].v;
if(v!=father) {
dfs1(v,u);
siz[u]+=siz[v];
if(son[u]==-1||siz[son[u]]<siz[v])
son[u]=v;
}
}
}
void dfs2(int u,int top) {
tp[u]=top;
f[u]=++cnt;
invf[f[u]]=u;
if(son[u]==-1)
return ;
dfs2(son[u],top);
for(int i=head[u]; ~i; i=e[i].next) {
int v=e[i].v;
if(v!=son[u]&&v!=fa[u]) {
dfs2(v,v);
}
}
}
void push_down(int root,int l,int r) {
if(~mark[root]) {
mark[lson]=mark[rson]=mark[root];
seg[lson].cnt=seg[rson].cnt=1;
seg[lson].l=seg[lson].r=seg[rson].l=seg[rson].r=mark[root];
mark[root]=-1;
}
}
void push_up(int root,int l,int r) {
seg[root].cnt=seg[lson].cnt+seg[rson].cnt;
if(seg[lson].r==seg[rson].l)
seg[root].cnt--;
seg[root].l=seg[lson].l;
seg[root].r=seg[rson].r;
}
void build(int root,int l,int r) {
if(l==r) {
seg[root].cnt=1;
seg[root].l=seg[root].r=node[invf[l]];
return ;
}
Mid;
build(lson,l,mid);
build(rson,mid+1,r);
push_up(root,l,r);
}
void update(int root,int l,int r,int ql,int qr,int val) {
if(l>qr||r<ql)
return;
if(l>=ql&&r<=qr) {
seg[root].cnt=1;
seg[root].l=seg[root].r=val;
mark[root]=val;
return ;
}
Mid;
push_down(root,l,r);
update(lson,l,mid,ql,qr,val);
update(rson,mid+1,r,ql,qr,val);
push_up(root,l,r);
}
void query(int root,int l,int r,int ql,int qr) {
if(l>qr||r<ql)
return;
if(l>=ql&&r<=qr) {
if(!ans) {
ans=seg[root].cnt;
rr=seg[root].r;
return;
}
ans+=seg[root].cnt;
if(rr==seg[root].l) ans--;
rr=seg[root].r;
return ;
}
Mid;
push_down(root,l,r);
query(lson,l,mid,ql,qr);
query(rson,mid+1,r,ql,qr);
push_up(root,l,r);
}
int cloquer(int root,int l,int r,int ql,int qr) {
int tmp=0;
if(l>qr||r<ql)
return 0;
if(l>=ql&&r<=qr) {
return seg[root].l;
}
Mid;
push_down(root,l,r);
tmp+=cloquer(lson,l,mid,ql,qr);
tmp+=cloquer(rson,mid+1,r,ql,qr);
push_up(root,l,r);
return tmp;
}
int main() {
//FREI;
//FREO;
while(scanf("%d%d",&n,&m)!=EOF) {
initsplit();
for(int i=1; i<=n; i++)
scanf("%d",&node[i]);
for(int i=1; i<n; i++) {
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs1(1,1);
dfs2(1,1);
build(1,1,n);
for(int i=0; i<m; i++) {
char x[10];
scanf("%s",x);
if(x[0]=='Q') {
int x,y;
scanf("%d%d",&x,&y);
res=0;
while(tp[x]!=tp[y]) {
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
ans=0;
query(1,1,n,f[tp[x]],f[x]);
res+=ans;
if(cloquer(1,1,n,f[tp[x]],f[tp[x]])==cloquer(1,1,n,f[fa[tp[x]]],f[fa[tp[x]]]))
res--;
x=fa[tp[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans=0;
query(1,1,n,f[x],f[y]);
res+=ans;
printf("%d\n",res);
} else {
int x,y,val;
scanf("%d%d%d",&x,&y,&val);
while(tp[x]!=tp[y]) {
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
update(1,1,n,f[tp[x]],f[x],val);
x=fa[tp[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update(1,1,n,f[x],f[y],val);
}
}
}
}
变量命名是关键啊 很早写完改好了 一直出错 原来是函数体里的一个变量和全局变量重名了 一直没发现 好累 浪费了超多的时间 好好注意
