题目链接 BZOJ3083
换根不能真正地换。
令当前的根为$cnt$，要查找的子树根为$x$
$1$、$x = cnt$，那么要查找的区域就是整棵树。
$2$、$x$在以$cnt$为根的子树内，那么要查找的区域就是以$x$为根的子树。
$3$、$x$在以$cnt$为根的子树外
（1）$x$不是$cnt$的祖先，那么要查找的区域就是以$x$为根的子树。
（2）$x$是$cnt$的祖先，设$y$为$x$到$cnt$方向上的第一个点，那么要查找的区域就是整棵树减去以$y$为根的子树。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define ls i << 1
#define rs i << 1 | 1
#define mid ((L + R) >> 1)
#define lson i << 1, L, mid
#define rson i << 1 | 1, mid + 1, R const int N = 1e5 + 10; int f[N], fp[N], son[N], deep[N], father[N], sz[N], a[N], top[N];
int n, m, tot = 0;
int cnt;
int s[N << 2], lazy[N << 2];
vector <int> v[N]; void dfs1(int x, int fa, int dep){
deep[x] = dep;
father[x] = fa;
son[x] = 0;
sz[x] = 1;
int ct = (int)v[x].size();
rep(i, 0, ct - 1){
int u = v[x][i];
if (u == fa) continue;
dfs1(u, x, dep + 1);
sz[x] += sz[u];
if (sz[son[x]] < sz[u]) son[x] = u;
}
} void dfs2(int x, int tp){
top[x] = tp;
f[x] = ++tot;
fp[f[x]] = x;
if (son[x]) dfs2(son[x], tp);
int ct = (int)v[x].size();
rep(i, 0, ct - 1){
int u = v[x][i];
if (u == father[x] || u == son[x]) continue;
dfs2(u, u);
}
} inline void pushup(int i){ s[i] = min(s[ls], s[rs]); } inline void pushdown(int i){
if (lazy[i]){
s[ls] = lazy[ls] = lazy[i];
s[rs] = lazy[rs] = lazy[i];
lazy[i] = 0;
}
} void update(int i, int L, int R, int l, int r, int val){
if (l <= L && R <= r){
s[i] = lazy[i] = val;
return;
} pushdown(i);
if (l <= mid) update(lson, l, r, val);
if (r > mid) update(rson, l, r, val);
pushup(i);
} int query(int i, int L, int R, int l, int r){
if (l <= L && R <= r) return s[i]; pushdown(i);
int ret = INT_MAX;
if (l <= mid) ret = min(ret, query(lson, l, r));
if (r > mid) ret = min(ret, query(rson, l, r));
return ret;
} void modify(int x, int y, int val){
int f1 = top[x], f2 = top[y];
for (; f1 ^ f2; ){
if (deep[f1] < deep[f2]) swap(f1, f2), swap(x, y);
update(1, 1, n, f[f1], f[x], val);
x = father[f1], f1 = top[x];
} if (x == y){
update(1, 1, n, f[x], f[y], val);
return;
} if (deep[x] > deep[y]) swap(x, y);
update(1, 1, n, f[x], f[y], val);
return; } int twz(int x, int y){
int t;
for (; top[x] ^ top[y]; ) t = top[y], y = father[top[y]];
return x == y ? t : son[x];
} int LCA(int x, int y){
for (; top[x] ^ top[y]; ){
if (deep[top[x]] < deep[top[y]]) swap(x, y);
x = father[top[x]];
} return deep[x] > deep[y] ? y : x;
} int main(){ scanf("%d%d", &n, &m); rep(i, 0, 4e5 + 10) s[i] = INT_MAX; rep(i, 2, n){
int x, y;
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
} dfs1(1, 0, 1);
dfs2(1, 1); rep(i, 1, n){
int x;
scanf("%d", &x);
update(1, 1, n, f[i], f[i], x);
} scanf("%d", &cnt); while (m--){
int op;
scanf("%d", &op);
if (op == 1) scanf("%d", &cnt);
else if (op == 2){
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
modify(x, y, z);
} else{
int x;
scanf("%d", &x);
if (x == cnt){
printf("%d\n", query(1, 1, n, 1, n));
continue;
} int lca = LCA(x, cnt);
if (lca == x){
int y = twz(x, cnt);
int ret = INT_MAX;
int xx = f[y], yy = f[y] + sz[y] - 1;
if (xx >= 1) ret = min(ret, query(1, 1, n, 1, xx - 1));
if (yy < n) ret = min(ret, query(1, 1, n, yy + 1, n));
printf("%d\n", ret);
continue;
} printf("%d\n", query(1, 1, n, f[x], f[x] + sz[x] - 1));
}
} return 0;
}