AC on #11#12求条

#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
const int N=1e5+5;
int n,m;
int dep[N],sz[N],hson[N],top[N];
struct node{
	int tag;
}t[N<<2];
void build(int p,int pl,int pr){
	t[p].tag=1;
	if(pl==pr){
		return;
	}
	int mid=(pl+pr)>>1;
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
}
void change(int p,int pl,int pr,int d){
    if(dep[t[p].tag]>dep[d]) return;
	t[p].tag=d;
}
void down(int p,int pl,int pr){
	int mid=(pl+pr)>>1;
	change(ls(p),pl,mid,t[p].tag);
	change(rs(p),mid+1,pr,t[p].tag);
}
void upd(int l,int r,int p,int pl,int pr,int d){
	if(l<=pl&&pr<=r){
		change(p,pl,pr,d);
		return;
	}
	down(p,pl,pr);
	int mid=(pl+pr)>>1;
	if(l<=mid) upd(l,r,ls(p),pl,mid,d);
	if(r>mid) upd(l,r,rs(p),mid+1,pr,d);
}
int q(int l,int r,int p,int pl,int pr){
	if(l<=pl&&pr<=r) return t[p].tag;
	down(p,pl,pr);
	int mid=(pl+pr)>>1;
	if(l<=mid) return q(l,r,ls(p),pl,mid);
	if(r>mid) return q(l,r,rs(p),mid+1,pr);
}
vector <int> e[N];
int pr[N],id[N],ord;
void dfs1(int u,int fa){
	dep[u]=dep[fa]+1;
	pr[u]=fa;
	sz[u]=1;
	for(int v:e[u]){
		if(v==fa) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(!hson[u]||sz[hson[u]]<sz[v]) hson[u]=v;
	}
}
void dfs2(int u,int topu){
	id[u]=++ord;
	top[u]=topu;
	if(!hson[u]) return;
	dfs2(hson[u],topu);
	for(int v:e[u]){
		if(v==pr[u]||v==hson[u]) continue;
		dfs2(v,v);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m;
	for(int i=2;i<=n;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	while(m--){
		char op;int u;
		cin>>op>>u;
		if(op=='C'&&dep[u]>dep[q(id[u],id[u],1,1,n)]) upd(id[u],id[u]+sz[u]-1,1,1,n,u);
		else cout<<q(id[u],id[u],1,1,n)<<'\n';
	}
	return 0;
}