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;
}