1.题目

2.分析

①操作一应该做的操作

我们可以知道，树上两点的路径 ( 路 径 上 的 点 的 集 合 记 作 l ) (路径上的点的集合记作l) (路径上的点的集合记作l) 是确定的，所以任意两个被标记的点之间的路径上的点 ( 记 作 x ) (记作x) (记作x) 的 f ( x ) f(x) f(x)，满足下面的等式

f ( i ) = f ( j ) ( i ∈ l ） f(i) = f(j) (i \in l） f(i)=f(j)(i∈l）

解释：这个等式相当于从 i i i走到 j j j后再前往任意一个被标记的点(但不走回头路)

所以我们可以在 l l l 集合选一个标兵(并查集的树根)，用 T a Ta Ta 来表示整个并查集(因为整个并查集的f(x)相等)

参考代码

void UnionSet (int x, int y) { 
	int u = FindSet (x), v = FindSet (y);
	if (u == v) return;
	fa[u] = v;
	_min[v] = Min (_min[u], _min[v]);
}

bool dfs (int u, int father) { 
	if (check (start, u)) return 1;
	for (int i = head[u]; i; i = e[i].next) { 
		int v = e[i].to;
		if (v == father) continue;
		bool flag = dfs (v, u);
		if (flag == 1) { 
			vis[u] = 1;
			UnionSet (start, u);
			return 1;
		}
	}
	return 0;
}

②操作二应该做的操作

将并查集记作 s s s

对于每个点的 f ( x ) f(x) f(x) ，我们可以得出

f ( x ) = M i n ( ( f ( j ) , d p ( x , j ) ) ( j ∈ s ) f(x) = Min ((f(j), dp(x, j))(j \in s) f(x)=Min((f(j),dp(x,j))(j∈s)

( d p ( x , j ) 表 示 x 走 到 j 的 路 径 上 的 点 的 最 小 值 ) (dp(x,j)表示x走到j的路径上的点的最小值) (dp(x,j)表示x走到j的路径上的点的最小值)

求 d i s ( x , j ) dis(x, j) dis(x,j)时我们可以用一个类似于并查集路径压缩的思想，得出下列转移式

d p ( x , j ) = M i n ( x , d p ( y , j ) ) ( y 是 x 的 子 节 点 ) dp(x, j) = Min (x, dp(y, j)) (y是x的子节点) dp(x,j)=Min(x,dp(y,j))(y是x的子节点)

同时，我们搜到一个点 j ( j ∈ s ) j(j \in s) j(j∈s) 时，还要保存这个点的编号 (去找 f ( j ) ∈ s f(j) \in s f(j)∈s)

同样可以用一个类似于并查集路径压缩的思想，得出下列转移式

i n d e x [ x ] = i n d e x [ y ] ( y 是 x 的 子 节 点 ) index[x] = index[y](y是x的子节点) index[x]=index[y](y是x的子节点)

i n d e x [ i ] 指 向 一 个 在 并 查 集 内 的 一 个 节 点 的 下 标 index[i]指向一个在并查集内的一个节点的下标 index[i]指向一个在并查集内的一个节点的下标

参考代码

int find_root (int u, int father)  { 
	if (check (u, start)) { 
		return u;
	}
	for (int i = head[u]; i; i = e[i].next) { 
		int v = e[i].to;
		if (v == father) continue;
		int flag = find_root (v, u);
		if (flag == -1) continue;
		index[u] = flag;
		dp[u] = Min (u, dp[v]);
		return flag;
	}
	return -1;
}

参考代码 (综上所述)

#include <cstdio> 
#include <iostream>
using namespace std;

const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int n, q, start = -1;
int fa[MAXN], _min[MAXN], index[MAXN], dp[MAXN];
//dp表示走到并查集的路径中的最小值 
bool vis[MAXN];
//vis[i] == 1表示i在并查集里面 

int len, head[MAXN];
struct edge { 
	int to, next;
}e[MAXN * 2];

int Min (int x, int y) {  return x < y ? x : y; }

int read () { 
	int x = 0, f = 1;
	char tem = getchar ();
	while (tem < '0' || tem > '9') { 
		if (tem == '-') f = -1;
		tem = getchar ();
	}
	while (tem >= '0' && tem <= '9') { 
		x = (x << 1) + (x << 3) + tem - '0';
		tem = getchar ();
	}
	return x * f;
}

void MakeSet () { 
	for (int i = 1; i <= n; i++) { 
		fa[i] = i;
		_min[i] = i;
		index[i] = i;
		dp[i] = INF;
	}
}

int FindSet (int x) { 
	if (fa[x] != x) { 
		fa[x] = FindSet (fa[x]);
	}
	return fa[x];
}

void UnionSet (int x, int y) { 
	int u = FindSet (x), v = FindSet (y);
	if (u == v) return;
	fa[u] = v;
	_min[v] = Min (_min[u], _min[v]);
}

bool check (int x, int y) { 
	int u = FindSet (x), v = FindSet (y);
	if (u == v) return 1;
	else return 0;
}

bool dfs (int u, int father) { 
	if (check (start, u)) return 1;
	for (int i = head[u]; i; i = e[i].next) { 
		int v = e[i].to;
		if (v == father) continue;
		bool flag = dfs (v, u);
		if (flag == 1) { 
			vis[u] = 1;
			UnionSet (start, u);
			return 1;
		}
	}
	return 0;
}

int find_root (int u, int father)  { 
	if (check (u, start)) { 
		return u;
	}
	for (int i = head[u]; i; i = e[i].next) { 
		int v = e[i].to;
		if (v == father) continue;
		int flag = find_root (v, u);
		if (flag == -1) continue;
		index[u] = flag;
		dp[u] = Min (u, dp[v]);
		return flag;
	}
	return -1;
}

void add (int x, int y) { 
	e[++len].to = y;
	e[len].next = head[x];
	head[x] = len;
}

int main () { 
	n = read (); q = read ();
	MakeSet ();
	for (int i = 1; i < n; i++) { 
		int x, y; x = read (); y = read ();
		add (x, y); add (y, x);
	}
	for (int i = 1; i <= q; i++) { 
		int type, x; type = read (); x = read ();
		if (type == 1) { 
			if (start == -1) { 
				start = x;
				continue;
			}
			dfs (x, -1);
		}
		else { 
			if (vis[x] == 0) { //不在并查集内 
				if (dp[x] == INF) { 
					find_root (x, -1);
				}
				printf ("%d\n", Min (dp[x], _min[FindSet (index[x])]));
			}
			else { //在并查集内 
				printf ("%d\n", _min[FindSet (x)]);
			}
		}
// for (int j = 1; j <= n; j++) printf ("root[%d] = %d, _min = %d\n", j, FindSet (j), _min[FindSet (j)]);
	}
	return 0;
}