记录编号	586570	评测结果	AAAAAAAAAAAA
题目名称	黑白树	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	3.559 s
提交时间	2024-02-07 19:07:44	内存使用	109.03 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+10;
int n,m;
struct made{
	int ver,nx,id;
}e[N<<1];
int hd[N],tot,cnt;
int size[N],dep[N],fa[N],son[N];
int dfn[N],rnk[N],top[N],tim[N];
void add(int x,int y,int id){
	tot++;
	e[tot].nx = hd[x],e[tot].ver = y,e[tot].id = id,hd[x] = tot;
}
void dfs1(int x){
	size[x] = 1;
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(y == fa[x])continue;
		dep[y] = dep[x] + 1,fa[y] = x;
		dfs1(y),size[x] += size[y],rnk[y] = e[i].id;
		if(!son[x] || size[y] > size[son[x]])son[x] = y;
	}
}
void dfs2(int x,int t){
	dfn[x] = ++cnt,top[x] = t;
	if(!son[x])return;
	dfs2(son[x],t);
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(y != fa[x] && y != son[x])dfs2(y,y);
	} 
}
int Lca(int x,int y){
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]])swap(x,y);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y])swap(x,y);
	return x;
}
struct B{
	int fa[N];
	inline void first(){
		for(int i = 1;i <= n;i++)fa[i] = i;
	}
	int find(int x){
		if(fa[x] == x)return x;
		return fa[x] = find(fa[x]);
	}
}B,W;
int q[N],ans[N];
vector<int>G[N];
void mark(int x,int y,int cur){
	if(tim[x])x = B.find(x);
	while(dep[x] > dep[y]){
		tim[x] = cur;
		int f =  B.find(fa[x]);
		B.fa[x] = f;
		x = f;
	}
}
int main(){
	freopen("bzoj_3319.in","r",stdin);
	freopen("bzoj_3319.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i < n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y,i),add(y,x,i); 
	}
	dep[1] = 1,dfs1(1),dfs2(1,1);
	B.first();
	for(int i = 1;i <= m;i++){
		int op,x,y;
		scanf("%d%d",&op,&x);
		if(op == 1)q[i] = x;
		else{
			scanf("%d",&y);
			int lca = Lca(x,y);
			mark(x,lca,i),mark(y,lca,i);
		}
	}
	W.first();
	for(int i = 1;i <= n;i++)G[tim[i]].push_back(i);
	for(int i = 0;i < G[0].size();i++)W.fa[G[0][i]] = W.find(fa[G[0][i]]);
	for(int i = m;i >= 1;i--){
		if(q[i])ans[i] = W.find(q[i]);
		else{
			for(int j = 0;j < G[i].size();j++)W.fa[G[i][j]] = W.find(fa[G[i][j]]);
		}
	}
	for(int i = 1;i <= m;i++)
	    if(q[i])printf("%d\n",rnk[ans[i]]);
	
	
	return 0;
	
}