记录编号	593860	评测结果	RRRRRRRRRR
题目名称	牛宫	最终得分	0
用户昵称	wdsjl	是否通过	未通过
代码语言	C++	运行时间	2.129 s
提交时间	2024-09-19 20:51:24	内存使用	5.06 MiB

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
const int INF = 0x7f7f7f7f;

struct E{
	int to,ne;
}e[N*2];

int tot,h[N],n,q,ying[N];

void add(int u,int v){
	e[tot]={v,h[u]};
	h[u]=tot++;
	e[tot]={u,h[v]};
	h[v]=tot++;
	return ;
} 

int fa[N],siz[N],son[N],dep[N];

void dfs1(int u,int f){
	fa[u]=f;
	siz[u]=1;
	dep[u]=dep[f]+1;
	int maxsiz=-1;
	for(int i=h[u];~i;i=e[i].ne){
		int v=e[i].to;
		if(v==f)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>maxsiz){
			maxsiz=siz[v];
			son[u]=v;
		}
	}
	return ;
}

int dfn[N],w[N],v[N],top[N],tim;

void dfs2(int u,int t){
	top[u]=t;
	dfn[u]=++tim;
	ying[tim]=u; 
	w[tim]=tim;
	if(!son[u])return ;
	dfs2(son[u],t);
	for(int i=h[u];~i;i=e[i].ne){
		int v=e[i].to;
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
} 

int minv[N*4];

void pushup(int k){
	minv[k]=min(minv[k*2],minv[k*2+1]);
} 

void build(int k,int l,int r){
	int mid=(l+r)>>1;
	if(l==r){
		minv[k]=INF;
		return ;
	}
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	pushup(k);
	return ;
}

void update(int k,int l,int r,int q,int v){
	int mid=(l+r)>>1;
	if(l==r){
		minv[k]=v;
		return ;
	}
	if(q<=mid)update(k*2,l,mid,q,v);
	else update(k*2+1,mid+1,r,q,v);
	pushup(k);
	return ;
}

int querymin(int k,int l,int r,int ql,int qr){
	int mid=(l+r)>>1,ans=INF;
	if(ql<=l&&r<=qr)return minv[k];
	if(ql<=mid)ans=min(ans,querymin(k*2,l,mid,ql,qr));
	if(qr>mid)ans=min(ans,querymin(k*2+1,mid+1,r,ql,qr));
	pushup(k);
	return ans;
}

int qmin(int u,int v){
	int ans=INF;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		ans=min(ans,querymin(1,1,n,dfn[top[u]],dfn[u]));
		u=fa[top[u]];
	}
	if(dep[u]<dep[v])swap(u,v);
	ans=min(ans,querymin(1,1,n,dfn[v],dfn[u]));
	return ans;
}

int main(){
	memset(minv,0x7f,sizeof(minv));
	memset(h,-1,sizeof(h));
	scanf("%d%d",&n,&q);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	dep[1]=1;
	fa[1]=1;
	dfs1(1,-1);
	dfs2(1,1);
	for(int i=1;i<=q;i++){
		int op,x;
		scanf("%d%d",&op,&x);
		if(op==0){
			if(qmin(x,x)==0x7f7f7f7f){
				update(1,1,n,dfn[x],dfn[x]);
			}else update(1,1,n,dfn[x],INF);
		}else if(op==1){
			if(qmin(1,x)==0x7f7f7f7f)printf("-1\n");
			else printf("%d\n",ying[qmin(1,x)]);
		}
	}
	return 0;
}