Ryan_<

//Ryan ___与孤独为伴,同清醒共舞.
int n,m;
int timer=0,st[N],ed[N],dep[N]; 
void dfs(int x,int ff)
{
	st[x]=++timer;
	dep[x]=dep[ff]+1;//根节点深度为1 
	R(i,x){
		int y=e[i].go;
		if(y==ff) continue;
		dfs(y,x);
	}
	ed[x]=timer;
}

#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
struct seg{int l,r,tag;}t[N<<2];
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;t[k].tag=1;
//	if(l==r){t[k].v=1;return;}
	if(l==r) return;
	int mid=l+r>>1;
	build(lson);build(rson);
}
int better(int x,int y){return dep[x]<dep[y]?y:x;}
void modify(int k,int lx,int rx,int val)//区间取max 
{
	int l=t[k].l,r=t[k].r;
	if(lx<=l&&r<=rx) t[k].tag=better(t[k].tag,val);//注意包含关系 
	else{
		int mid=l+r>>1;//t[k].l t[k].r
		if(lx<=mid) modify(k<<1,lx,rx,val);
		if(rx>mid) modify(k<<1|1,lx,rx,val);
	}
}
int query(int k,int pos)//单点查询 
{
	int l=t[k].l,r=t[k].r;
	if(l==r) return t[k].tag;
	int mid=l+r>>1,ans=t[k].tag;
	if(pos<=mid) return better(ans,query(k<<1,pos));
	else return better(ans,query(k<<1|1,pos));
}

int main()
{
//	freopen("tree.txt","r",stdin);
	n=read();m=read();
	F(i,1,n-1){
		int x=read(),y=read();
		addedge(x,y);
	}
	dfs(1,0);
	build(1,1,n);
	while(m--){
		char op[5];int x;
		scanf("%s",op);x=read();
		if(op[0]=='C') modify(1,st[x],ed[x],x);
		else if(op[0]=='Q') printf("%d\n",query(1,st[x]));
	}
	return 0;
}

题意:给定一棵n个节点的数，要求资瓷m个操作，操作有两种：

1. 对某个结点打上标记

2. 询问某个结点最近的一个打了标记的祖先

n,m<=10^5