思路
一道树链剖分不好题。
爆零小技巧：设置最大值比给出序列的最大值还小
如果没有修改根的操作，那必定是个树链剖分板子题，只需要求线段树区间最小值，以及进行区间修改即可。
但是，有了换根操作就有了麻烦，不过可以发现一个小性质，那就是不管根是什么，一个点 (x) 到另一点 (y) 的路径都是不变的。
所以就可以直接以(1)为根进行树剖，每次修改时像普通树剖一样进行修改，所以现在的问题就是如何处理查询操作。
设当前要查询的节点为 (x)，当前的根为 (root)，在查询时分多种情况：
- (root) 等于 (x) 时，直接输出全局最小值
- (root) 不在 (x) 的子树中时，(x) 的子树还是以 (1) 为根时的子树，直接对 (x) 进行查询
- (root) 在 (x) 的子树当中时，(x) 的子树中不能访问到的是 (root) 所在支链，求出 (x) 在 (root) 支链处的儿子 (sonn)，因为在 (dfn) 序中，一个点以及其子树内所有点的编号是连续的，所以直接求(1sim dfn[sonn]-1) 中的最小值和 (dfn[sonn] + siz[sonn]sim n)中的最小值，取 (min) 即可
时间复杂度 (O(nlog^2 n))
代码
/*
Author:loceaner
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 2e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x7fffffff;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, m, root, cnt, pre[A], val[A], head[A];
struct node { int to, nxt; } e[A << 1];
inline void add(int from, int to) {
e[++cnt].to = to;
e[cnt].nxt = head[from];
head[from] = cnt;
}
namespace Seg {
#define lson rt << 1
#define rson rt << 1 | 1
struct tree { int l, r, minn, lazy; } t[A << 2];
inline void pushup(int rt) {
t[rt].minn = min(t[lson].minn, t[rson].minn);
}
inline void pushdown(int rt) {
t[lson].minn = t[rt].lazy;
t[rson].minn = t[rt].lazy;
t[lson].lazy = t[rt].lazy;
t[rson].lazy = t[rt].lazy;
t[rt].lazy = 0;
}
void build(int rt, int l, int r) {
t[rt].l = l, t[rt].r = r, t[rt].lazy = 0;
if (l == r) {
t[rt].minn = val[pre[l]];
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
pushup(rt);
}
void update(int rt, int l, int r, int k) {
if (l <= t[rt].l && t[rt].r <= r) {
t[rt].lazy = t[rt].minn = k;
return;
}
if (t[rt].lazy) pushdown(rt);
int mid = (t[rt].l + t[rt].r) >> 1;
if (l <= mid) update(lson, l, r, k);
//debug: l, r 写成 l, mid
if (r > mid) update(rson, l, r, k);
//debug: l, r 写成 mid + 1, r
pushup(rt);
}
int query(int rt, int l, int r) {
if (l <= t[rt].l && t[rt].r <= r) return t[rt].minn;
if (t[rt].lazy) pushdown(rt);
int mid = (t[rt].l + t[rt].r) >> 1, ans = inf;
if (l <= mid) ans = min(ans, query(lson, l, r));
//debug: l, r 写成 l, mid
if (r > mid) ans = min(ans, query(rson, l, r));
//debug: l, r 写成 mid + 1, r
return ans;
//爆零小技巧：在有返回值的函数中不加return
}
}
int dfscnt, dep[A], fa[A], siz[A], son[A], dfn[A], top[A];
void prepare(int x, int f) {
siz[x] = 1, fa[x] = f, dep[x] = dep[f] + 1;
for (int i = head[x]; i; i = e[i].nxt) {
int to = e[i].to;
if (to == f) continue;
prepare(to, x), siz[x] += siz[to];
if (siz[to] > siz[son[x]]) son[x] = to;
}
}
void dfs(int x, int tp) {
dfn[x] = ++dfscnt, pre[dfscnt] = x, top[x] = tp;
if (son[x]) dfs(son[x], tp);
for (int i = head[x]; i; i = e[i].nxt) {
int to = e[i].to;
if (to == fa[x] || to == son[x]) continue;
dfs(to, to);
}
}
inline void upd(int x, int y, int val) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
Seg::update(1, dfn[top[x]], dfn[x], val);
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
Seg::update(1, dfn[x], dfn[y], val); return;
}
inline int prove(int x) {
if (root == x) return 1;
if (dfn[root] <= dfn[x] || dfn[root] > dfn[x] + siz[x] - 1) return 2;
return 0;
}
inline void solve(int x) {
int flag = prove(x);
// cout << flag << " ";
if (flag == 1) cout << Seg::t[1].minn << '
';
else if (flag == 2) cout << Seg::query(1, dfn[x], dfn[x] + siz[x] - 1) << '
';
else {
int now = root, sonn = 0;
while (top[now] != top[x]) {
if (fa[top[now]] == x) { sonn = top[now]; break; }
now = fa[top[now]];
}
if (!sonn) sonn = son[x];
int ans = Seg::query(1, 1, dfn[sonn] - 1);
if (dfn[sonn] + siz[sonn] - 1 != n)
ans = min(ans, Seg::query(1, dfn[sonn] + siz[sonn], n));
cout << ans << '
';
}
}
int main() {
// freopen("a.in", "r", stdin);
// freopen("1.out", "w", stdout);
n = read(), m = read();
for (int i = 1; i < n; i++) {
int x = read(), y = read();
add(x, y), add(y, x);
}
for (int i = 1; i <= n; i++) val[i] = read();
prepare(1, 0), dfs(1, 1), Seg::build(1, 1, n);
root = read();
while (m--) {
int opt = read(), x = read(), y, val;
if (opt == 1) root = x;
else if (opt == 2) y = read(), val = read(), upd(x, y, val);
else if (opt == 3) solve(x);
}
return 0;
}