fa表示父亲节点

id表示dfs序

gs表示重儿子编号

st表示树链的根

rid表示真实的编号

lp表示区间内编号最 小的点的编号

dfs处理fa、size、gs

dfs2处理st、id、rid

change改变节点颜色&更新lp

get_min获取编号最小的黑色点的编号

ans得到答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,q,u,v,fa[MAXN],id[MAXN],size[MAXN],gs[MAXN],st[MAXN],nidx=1,rid[MAXN],
                                                           lp[MAXN];
vector<int>to[MAXN];
bool col[MAXN]; // 0:white 1:black
int read() {
	int sum = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') sum = (sum<<3) + (sum<<1)+(ch^48), ch = getchar();
	return sum; 
}
void dfs(int from,int idx) { // father && size && gson
	fa[idx]=from;
	if(to[idx].size()==1&&to[idx].at(0)==from) {
		size[idx]=1;
		gs[idx]=idx;
		return;
	}
	size[idx]=1;
	int ms=0;
	for(int i=0; i<to[idx].size(); i++)
		if(to[idx].at(i)!=from) {
			dfs(idx,to[idx].at(i));
			size[idx]+=size[to[idx].at(i)];
			if(size[to[idx].at(i)]>ms) {
				ms=size[to[idx].at(i)];
				gs[idx]=to[idx].at(i);
			}
		}
}
void dfs2(int from,int from2,int idx) { // start && id
//	cerr<< from << from2 << idx<<endl;
	st[idx]=from2;
	id[idx]=nidx;
	rid[nidx]=idx;
	nidx++;
	if(to[idx].size()==1&&to[idx].at(0)==from)
		return;
	dfs2(idx,from2,gs[idx]);
	for(int i=0; i<to[idx].size(); i++)
		if(to[idx].at(i)!=from&&to[idx].at(i)!=gs[idx])
			dfs2(idx,to[idx].at(i),to[idx].at(i));
}
void change(int pos,int lt,int rt,int idx) {
	if(lt==rt) {
		col[lt]=1-col[lt];
		if(col[lt])
			lp[idx]=lt;
		else
			lp[idx]=-1;
		if(lt == rt) {
		}
		return;
	}
	int mid=(lt+rt)>>1;
	if(pos<=mid)
		change(pos,lt,mid,idx<<1);
	else
		change(pos,mid+1,rt,idx<<1|1);
	if(lp[idx<<1]!=-1)
		lp[idx]=lp[idx<<1];
	else if(lp[idx<<1|1]!=-1)
		lp[idx]=lp[idx<<1|1];
	else
		lp[idx]=-1;
}
void init() {
	for(int i=1; i<=n*4; i++)
		lp[i]=-1;
}
int get_min(int st,int en,int lt,int rt,int idx) {
	if(st<=lt&&rt<=en)
		return lp[idx];
	int mid=(lt+rt)>>1;
	if(en<=mid)
		return get_min(st,en,lt,mid,idx<<1);
	if(st>mid)
		return get_min(st,en,mid+1,rt,idx<<1|1);
	int res1=get_min(st,en,lt,mid,idx<<1);
	int res2=get_min(st,en,mid+1,rt,idx<<1|1);
	if(res1!=-1)
		return res1;
	return res2;
}
int ans(int pos) {
	int res=0x7fffffff;
	if(col[pos]) res=min(res,pos);
	while(pos!=1) {
		/*
		if(id[st[rid[pos]]]==pos) { // pos=gson
			pos=id[fa[rid[pos]]];
			if(col[pos]) res=min(res,pos);
		} else {
			int rs=get_min(id[st[rid[pos]]],pos,1,n,1);
//			printf("get_min(st=%d, en=%d)->res=%d\n",id[st[rid[pos]]],pos,rs);
			if(rs!=-1)
				res=min(res,rs);
			pos=id[st[rid[pos]]];
		}
//		cerr<<"pos:"<<pos<<endl;
		int rs=get_min(id[st[rid[pos]]],pos,1,n,1);
		*/
		int rs=get_min(id[st[rid[pos]]],pos,1,n,1);
//		printf("get_min(st=%d, en=%d)->res=%d\n",id[st[rid[pos]]],pos,rs);
		if(rs!=-1) res=min(res,rs);
		pos=id[fa[st[rid[pos]]]];
	}
	if(col[pos]) res=min(res,pos);
	if(res!=0x7fffffff)
		return rid[res];
	return -1;
}
int main() {
//	freopen("in.in", "r", stdin);
//	freopen("A.out", "w", stdout);
	ios::sync_with_stdio(0);
	n = read(), q = read();
	init();
	for(int i=1; i<n; i++) {
		u = read(), v = read();
		to[u].push_back(v);
		to[v].push_back(u);
	}
	dfs(1,1);
//	cerr<<"DFS1 FIN\n";
//	for(int i=1; i<=n; i++) {
//		cerr<<"#"<<i<<":fa="<<fa[i]<<",size="<<size[i]<<",gson="<<gs[i]<<endl;
//	}
	dfs2(1,1,1);
//	cerr<<"DFS2 FIN\n";
//	for(int i=1; i<=n; i++)
//		cerr<<id[i]<<' ';
//	cerr<<endl;
	while(q--) {
		u = read(), v = read();
		if(u==0) {
			change(id[v],1,n,1);
		} else {
			cout<<ans(id[v])<<endl;
		}
	}
	return 0;
}
/*
5 4
4 3
5 2
1 5
3 1
0 3
1 3
1 1
1 4

*/