萌新刚学OI 1s，求条 P3979 遥远的国度

#include<bits/stdc++.h>
using namespace std;
vector<int> g[100005];
multiset<int> aux[100005];
int n, m, o, x, y, z, rt, a[100005], fa[100005], rev[100005], tag[100005], val[100005], ch[100005][2];
bool get(int x)
{
	return x == ch[fa[x]][1];
}
bool isroot(int x)
{
	return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
}
void pushup(int x)
{
	val[x] = min({*aux[x].begin(), val[ch[x][0]], val[ch[x][1]]});
}
void revdown(int x)
{
	swap(ch[x][0], ch[x][1]);
	rev[x] ^= 1;
}
void tagdown(int x, int y)
{
	aux[x].erase(aux[x].find(a[x]));
	a[x] = y;
	aux[x].insert(a[x]);
	tag[x] = y;
	val[x] = *aux[x].begin();
}
void pushdown(int x)
{
	if (tag[x])
	{
		if (ch[x][0])
		{
			tagdown(ch[x][0], tag[x]);
		}
		if (ch[x][1])
		{
			tagdown(ch[x][1], tag[x]);
		}
		tag[x] = 0;
	}
	if (rev[x])
	{
		if (ch[x][0])
		{
			revdown(ch[x][0]);
		}
		if (ch[x][1])
		{
			revdown(ch[x][1]);
		}
		rev[x] = 0;
	}
}
void rotate(int x)
{
	int y = fa[x], z = fa[y], d = get(x);
	if (isroot(y) == 0)
	{
		ch[z][get(y)] = x;
	}
	ch[y][d] = ch[x][d ^ 1];
	fa[ch[x][d ^ 1]] = y;
	ch[x][d ^ 1] = y;
	fa[y] = x;
	fa[x] = z;
	pushup(y);
	pushup(x);
}
void update(int x)
{
	if (isroot(x) == 0)
	{
		update(fa[x]);
	}
	pushdown(x);
}
void splay(int x)
{
	update(x);
	for (; isroot(x) == 0; rotate(x))
	{
		if (isroot(fa[x]) == 0)
		{
			rotate(get(x) == get(fa[x]) ? fa[x] : x);
		}
	}
}
void access(int x)
{
	for (int i = 0; x; i = x, x = fa[x])
	{
		splay(x);
		if (ch[x][1])
		{
			aux[x].insert(val[ch[x][1]]);
		}
		ch[x][1] = i;
		if (ch[x][1])
		{
			aux[x].erase(aux[x].find(val[ch[x][1]]));
		}
		pushup(x);
	}
}
void makeroot(int x)
{
	access(x);
	splay(x);
	revdown(x);
}
void split(int x, int y)
{
	makeroot(x);
	access(y);
	splay(y);
}
void dfs(int x, int p)
{
	aux[x].insert(a[x]);
	for (int i = 0; i < g[x].size(); i++)
	{
		int y = g[x][i];
		if (y == p)
		{
			continue;
		}
		dfs(y, x);
		fa[y] = x;
		aux[x].insert(val[y]);
	}
	pushup(x);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m; 
	val[0] = INT_MAX;
	for (int i = 1; i < n; i++)
	{
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	cin >> rt;
	dfs(rt, -1);
	while (m--)
	{
		cin >> o >> x;
		if (o == 1)
		{
			rt = x;
			makeroot(rt);
		}
		else if (o == 2)
		{
			cin >> y >> z;
			split(x, y);
			tagdown(y, z);
			makeroot(rt);
		}
		else
		{
			access(x);
			splay(x);
			cout << *aux[x].begin() << "\n";
		}
	}
	return 0;
}