还是发下完整代码吧
```cpp
#include<bits/stdc++.h>
#define ll long long
#define lc(k) k<<1
#define rc(k) k<<1|1
//#define int long long
const int MAX=1e5+10;
using namespace std;
inline int read() {
int fh = 1, res = 0; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
res = res * fh;
return res;
}
inline void write(ll x) {
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int top[MAX],fa[MAX],son[MAX],pre[MAX],dfn[MAX],deep[MAX],siz[MAX];
struct node{int l,r,w,f;}a[MAX<<2];
vector<int> s[MAX];
int cnt,ans,w[MAX];
void dfs1(int f,int k)
{
fa[k]=f;siz[k]=1;
deep[k]=deep[f]+1;
for(int i=0,sizz=s[k].size();i<sizz;i++)
{
int v=s[k][i];
if(v==f) continue;
dfs1(k,v);
siz[k]+=siz[v];
if(siz[v]>siz[son[k]])
son[k]=v;
}
return ;
}
void dfs2(int t,int k)
{
top[k]=t;
dfn[k]=++cnt;pre[cnt]=k;
if(son[k]) dfs2(t,son[k]);
for(int i=0,sizz=s[k].size();i<sizz;i++)
{
int v=s[k][i];
if(v==fa[k]||v==son[k]) continue;
dfs2(v,v);
}
return ;
}
void down(int k)
{
a[lc(k)].w+=(a[lc(k)].r-a[lc(k)].l+1)*a[k].f;
a[rc(k)].w+=(a[rc(k)].r-a[rc(k)].l+1)*a[k].f;
a[lc(k)].f+=a[k].f;a[rc(k)].f+=a[k].f;
a[k].f=0;
}
void build(int l,int r,int k)
{
a[k].l=l;a[k].r=r;
if(l==r) return ;
int mid=(l+r)>>1;
build(l,mid,lc(k));
build(mid+1,r,rc(k));
return ;
}
void change(int l,int r,int k,int z)
{
if(a[k].l>=l&&a[k].r<=r)
{
a[k].w+=(a[k].r-a[k].l+1)*z;
a[k].f+=z;
return ;
}
if(a[k].f) down(k);
int mid=(a[k].l+a[k].r)>>1;
if(l<=mid) change(l,r,lc(k),z);
if(mid+1<=r) change(l,r,rc(k),z);
a[k].w=a[lc(k)].w+a[rc(k)].w;
return ;
}
void ask(int l,int r,int k)
{
if(a[k].l>=l&&a[k].r<=r)
{
ans+=a[k].w;
return ;
}
if(a[k].f) down(k);
int mid=(a[k].l+a[k].r)>>1;
if(l<=mid) ask(l,r,lc(k));
if(mid+1<=r) ask(l,r,rc(k));
return ;
}
signed main()
{
int n=read();
int q=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
s[u].push_back(v);
// s[v].push_back(u);
}
dfs1(0,1);
dfs2(1,1);
build(1,n,1);
while(q--)
{
char opt;
cin>>opt;
if(opt=='C')
{
int x=read();
change(dfn[x],dfn[x],1,1);
}
if(opt=='Q')
{
ans=0;
int u=read();
ask(dfn[u],dfn[u],1);
if(ans)
{
printf("%d\n",u);
continue;
}
while(top[u]!=1)
{
ask(dfn[top[u]],dfn[u],1);
if(ans!=0) break;
u=fa[top[u]];
}
ask(1,dfn[u],1);
if(ans==0)
{
puts("1");
continue;
}
int l=dfn[top[u]],r=dfn[u],mid;
while(l<=r)
{
ans=0;
mid=(l+r)>>1;
ask(l,mid,1);
if(ans!=0) r=mid-1;
else l=mid+1;
}
printf("%d\n",l);
}
}
return 0;
}
```
by Surge_of_Force @ 2021-12-26 16:56:47