Tree
#include<iostream>
#include<cstring>
#include<cmath>
#include<stdlib.h>
#include<cstdio>
# define PI 3.14159265358979323846
#define int long long
#define qc std::ios::sync_with_stdio(false)
using namespace std;
const int maxl=300100;
const int minl=-217483648;
const int mod=1000000;
int n,m,q;
struct edge{
int to,next;
edge(){
to=next=0;
}
};
struct node
{
bool z;
int v,depth,son,zson;
int pre;//对应重链序的下表
int top;//头结点位置
int fa;//父节点
node(){
z=false;
v=0,depth=0,son=0;
pre=0;
}
};
struct zro{
static int cnt;
static int ni;
static bool debug_is_off;
zro(){
cnt=0;
ni=0;
debug_is_off=false;
}
};
struct seg_t
{
int r,l,mid;
int color;
int lc,rc;
int tag;
};
int zro::cnt=0;
int zro::ni=0;
bool zro::debug_is_off=false;
edge e[maxl<<1]; zro zr;
node n_[maxl<<1];
seg_t tree[maxl<<2];
int v[maxl<<1], head[maxl<<1],ys[maxl<<1];
void addedge(int u,int v){
e[++zr.cnt].next=head[u];
e[zr.cnt].to=v;
head[u]=zr.cnt;
}
void dfs1(int node,int depth,int f){
int son=0,ma=0,mi=0;
n_[node].depth=depth;
for(int i=head[node];i!=0;i=e[i].next){
if(e[i].to==f)continue;
dfs1(e[i].to,depth+1,node);
son+=n_[e[i].to].son+1;
if(n_[e[i].to].son>=ma){
ma=n_[e[i].to].son,mi=e[i].to;
}
}
n_[mi].z=true;
n_[node].zson=mi;
n_[node].son=son;
n_[node].fa=f;
}
void dfs2(int node,int top){
ys[++zr.ni]=node;
n_[node].pre=zr.ni;
int z=n_[node].zson;
if(node==1)n_[node].top=node;
else if(n_[node].z)n_[node].top=n_[n_[node].fa].top;
else n_[node].top=node;
if(z)dfs2(z,node);
for(int i=head[node];i!=0;i=e[i].next){
if(e[i].to==n_[node].fa||n_[e[i].to].z)continue;
dfs2(e[i].to,node);
}
}
void pushdown(int k){
// cout<<"pushdown: "<<k<<" tag: "<<tree[k].tag<<endl;
if(tree[k].tag!=-1){
if(tree[k].l==tree[k].r){
n_[ys[tree[k].l]].v=tree[k].tag;
tree[k].lc=tree[k].rc=tree[k].tag;
// cout<<"kkkkkkkkkkkkkkkindex"<<tree[k].l<<endl;
tree[k].tag=-1;
return;
}
tree[k<<1|1].color=tree[k<<1].color=1;
tree[k<<1|1].tag=tree[k<<1].tag=tree[k].tag;
tree[k<<1|1].lc=tree[k<<1|1].rc=tree[k<<1].lc=tree[k<<1].rc=tree[k].tag;
tree[k].tag=-1;
//cout<<"pushdown: "<<tree[k<<1].lc<<endl;
}
}
int tree_onclo(int k,int index){
//if(index==1)cout<<"fuckwhyerror:"<<k<<endl;
if(tree[k].l==tree[k].r){
// cout<<" index"<<index<<" v "<<tree[k].lc<<endl;
return tree[k].lc;
}
pushdown(k);
int mid=(tree[k].l+tree[k].r)>>1;
if(index<=mid)return tree_onclo(k<<1,index);
if(index>mid)return tree_onclo(k<<1|1,index);
return 0;
}
void pushup(int k){
if(tree[k<<1].rc==tree[k<<1|1].lc)tree[k].color=tree[k<<1].color+tree[k<<1|1].color-1;
else tree[k].color=tree[k<<1].color+tree[k<<1|1].color;
tree[k].lc=tree[k<<1].lc;
tree[k].rc=tree[k<<1|1].rc;
}
void build(int k,int l,int r){
tree[k].l=l;tree[k].r=r,tree[k].tag=-1;
if(l==r)
{
tree[k].color=1;
tree[k].lc=tree[k].rc=n_[ys[l]].v;
// cout<<" l "<<l<<" r "<<r<<" v "<<tree[k].lc<<endl;
tree[k].tag=-1;
//cout<<tree[k].tag<<endl;
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
pushup(k);
}
void tree_update(int k,int l,int r,int v){
//cout<<"tree_update: "<<" k :"<<k<<" l :"<<tree[k].l<<" r: "<<tree[k].r<<" v: "<<v<<endl;
// cout<<l<<"<--->"<<r<<endl;
if(tree[k].r<=r&&tree[k].l>=l){
tree[k].color=1;
tree[k].lc=tree[k].rc=v;
tree[k].tag=v;
// cout<<tree[k].l<<"--"<<tree[k].r<<endl;
// cout<<"tree["<<k<<"].tag==";
// cout<<tree[k].tag<<endl;
return;
}
pushdown(k);
int mid=(tree[k].l+tree[k].r)>>1;
if(l<=mid)tree_update(k<<1,l,r,v);
if(r>mid)tree_update(k<<1|1,l,r,v);
pushup(k);
}
int tree_color(int k,int l,int r){
if(tree[k].l>=l&&tree[k].r<=r){
return tree[k].color;
}
pushdown(k);
int mid=(tree[k].l+tree[k].r)>>1;
int color=maxl;
if(l<=mid)color=min(color,tree_color(k<<1,l,r));
if(r>mid)color=min(color,tree_color(k<<1|1,l,r));
return color;
}
int find_color(int l,int r){
int maxnum=0;
if(n_[l].top==n_[r].top)maxnum= tree_color(1,min(n_[l].pre,n_[r].pre),max(n_[l].pre,n_[r].pre));
else if(n_[n_[l].top].depth>=n_[n_[r].top].depth){
maxnum= find_color(l,n_[l].top)+find_color(n_[n_[l].top].fa,r);
int topc=tree_onclo(1,n_[n_[l].top].pre),fac=tree_onclo(1,n_[n_[n_[l].top].fa].pre);
// cout<<"l-------"<<n_[n_[l].top].pre<<"/"<<n_[n_[n_[l].top].fa].pre<<endl;
// cout<<"twoclo:"<<topc<<"-----"<<fac;
if(topc==fac)maxnum-=1;
}
else{
maxnum= find_color(r,n_[r].top)+find_color(l,n_[n_[r].top].fa);
int topc=tree_onclo(1,n_[n_[r].top].pre),fac=tree_onclo(1,n_[n_[n_[r].top].fa].pre);
//cout<<"l-------"<<n_[n_[r].top].pre<<"/"<<n_[n_[n_[r].top].fa].pre<<endl;
// cout<<"twoclo:"<<topc<<"-----"<<fac;
if(topc==fac)maxnum-=1;
}
// cout<<"findc "<<l<<"---"<<r<<" =="<<maxnum<<endl;
return maxnum;
}
void update(int l,int r,int v){
int il=n_[l].pre,ir=n_[r].pre;
tree_update(1,min(il,ir),max(il,ir),v);
}
void init(){
memset(e,0,sizeof(e));
memset(n_,0,sizeof(n));
memset(tree,0,sizeof(tree));
memset(v,0,sizeof(v));
memset(head,0,sizeof(head));
memset(ys,0,sizeof(ys));
zr.cnt=0;
zr.ni=0;
}
signed main(){
// qc;
while(cin>>n>>q){
init();
for(int i=1;i<=n;i++){
scanf("%d",&n_[i].v);
}
for(int i=1;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
}
dfs1(1,1,0);
dfs2(1,0);
build(1,1,n);
// debug();
for(int i=1;i<=q;i++){
char c[2];
int a,b,v;
scanf("%s",c);
scanf("%d%d",&a,&b);
if(c[0]=='C'){
scanf("%d",&v);
update(a,b,v);
}
else {
int ans=find_color(a,b);
printf("%d\n",ans);
}
}
}
/*
8
1 2 1 3
2 4 2 5
3 6 3 7
4 8
1 2 3 4 5 6 7 8
*/
}
网友评论