这道题还是很简单的，可以树剖，然后还有看大佬暴力模拟AC的？？？？！！
我们就执行俩操作，一个是单点修改，这个随便修，然后就是查询一个点，离他最近的被打过标记过的祖先。这个可以这么想，我们先query这个点所在链上的权值，如果>0就说明这条链上肯定是有至少一个被改过的点的。然后直接在区间之内左右二分即可。
（我不会告诉你我一开始想的是什么主席树维护的）
然后树剖写了这么多，就是要注意两点：
1.树剖和线段树千万别写错了……
2.一定要分清原顺序和dfs序，线段树维护的是dfs序，但是实际问题往往要求原顺序，这个一定别搞混！否则会死很惨还不一定能很快调出来。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 100005; const int mod = 1000000007; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct edge { int next,to; }e[M<<1]; struct seg { int v; }t[M<<2]; int n,q,x,y,head[M],ecnt,hson[M],size[M],top[M],dep[M],idx,rk[M],dfn[M],fa[M]; char s[5]; void add(int x,int y) { e[++ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; } void dfs1(int x,int f,int depth) { size[x] = 1,fa[x] = f,dep[x] = depth; int maxson = -1; for(int i = head[x];i;i = e[i].next) { if(e[i].to == f) continue; dfs1(e[i].to,x,depth+1); size[x] += size[e[i].to]; if(size[e[i].to] > maxson) maxson = size[e[i].to],hson[x] = e[i].to; } } void dfs2(int x,int t) { top[x] = t,dfn[x] = ++idx,rk[idx] = x; if(!hson[x]) return; dfs2(hson[x],t); for(int i = head[x];i;i = e[i].next) { if(e[i].to == fa[x] || e[i].to == hson[x]) continue; dfs2(e[i].to,e[i].to); } } void modify(int p,int l,int r,int pos) { if(l == r) { t[p].v = 1; return; } int mid = (l+r) >> 1; if(pos <= mid) modify(p<<1,l,mid,pos); else modify(p<<1|1,mid+1,r,pos); t[p].v = t[p<<1].v + t[p<<1|1].v; } int query(int p,int l,int r,int kl,int kr) { if(l == kl && r == kr) return t[p].v; int mid = (l+r) >> 1; if(kr <= mid) return query(p<<1,l,mid,kl,kr); else if(kl > mid) return query(p<<1|1,mid+1,r,kl,kr); else return query(p<<1,l,mid,kl,mid) + query(p<<1|1,mid+1,r,mid+1,kr); } int check(int l,int r) { if(l == r) return l; int mid = (l+r) >> 1; int g = query(1,1,n,mid+1,r); if(g) return check(mid+1,r); else return check(l,mid); } int qrange(int x,int y) { while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x,y); int g = query(1,1,n,dfn[top[x]],dfn[x]); if(!g) x = fa[top[x]]; else return check(dfn[top[x]],dfn[x]); } if(dep[x] > dep[y]) swap(x,y); return check(dfn[x],dfn[y]); } int main() { n = read(),q = read(); rep(i,1,n-1) x = read(),y = read(),add(x,y),add(y,x); dfs1(1,0,1),dfs2(1,1); while(q--) { scanf("%s",s); if(s[0] == 'C') x = read(),modify(1,1,n,dfn[x]); else x = read(),printf("%d ",rk[qrange(x,1)]); } return 0; }