为什么第 50 行一定要是小于号?
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,fa[100005],dep[100005],siz[100005],son[100005];
int top[100005],id[100005],cnt=0;
vector<int> g[100005];
inline void dfs1(int u,int f){
dep[u]=dep[f]+1;
siz[u]=1;
fa[u]=f;
int maxx=-1;
for(register int v:g[u]){
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>maxx) maxx=siz[v],son[u]=v;
}
return;
}
inline void dfs2(int u,int topf){
top[u]=topf;
id[u]=++cnt;
if(!son[u]) return;
dfs2(son[u],topf);
for(register int v:g[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
return;
}
struct Segment_Tree{
int t[400005],tag[400005];
inline void pushdown(int p){
t[p<<1]=dep[tag[p]]>dep[t[p<<1]]?tag[p]:t[p<<1];
t[p<<1|1]=dep[tag[p]]>dep[t[p<<1|1]]?tag[p]:t[p<<1|1];
tag[p<<1]=dep[tag[p]]>dep[tag[p<<1]]?tag[p]:t[p<<1];
tag[p<<1|1]=dep[tag[p]]>dep[tag[p<<1|1]]?tag[p]:t[p<<1|1];
tag[p]=0;
}
inline void update(int L,int R,int l,int r,int p,int k){
if(L<=l&&r<=R){
t[p]=(dep[t[p]]>dep[k])?t[p]:k;
tag[p]=(dep[tag[p]]>dep[k])?tag[p]:k;
return;
}
int mid=(l+r)>>1;
pushdown(p);
if(L<=mid&&dep[k]>dep[t[p<<1]]) update(L,R,l,mid,p<<1,k);
if(R>mid&&dep[k]>dep[t[p<<1|1]]) update(L,R,mid+1,r,p<<1|1,k);
t[p]=(dep[t[p<<1]]<dep[t[p<<1|1]])?t[p<<1]:t[p<<1|1];
return;
}
inline int query(int L,int R,int l,int r,int p){
if(L<=l&&r<=R) return t[p];
int mid=(l+r)>>1;
pushdown(p);
if(L<=mid) return query(L,R,l,mid,p<<1);
if(R>mid) return query(L,R,mid+1,r,p<<1|1);
}
}tree;
inline void print(){
for(int i=1;i<=n;i++) cout<<tree.query(i,i,1,n,1)<<' ';
cout<<endl;
}
signed main(){
scanf("%lld%lld",&n,&q);
for(register int i=1;i<n;i++){
int u,v;
scanf("%lld%lld",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0);
dfs2(1,1);
tree.update(id[1],id[1]+siz[1]-1,1,n,1,1);
while(q--){
char op;int x;
cin>>op>>x;
if(op=='C') tree.update(id[x],id[x]+siz[x]-1,1,n,1,x);
if(op=='Q') printf("%lld\n",tree.query(id[x],id[x],1,n,1));
}
return 0;
}