树剖已经是人尽皆知的sb题了吗……
很早以前就想填掉这坑了……
考虑到树链唯一，进行操作并不会对换根产生影响，那么我们的换根操作只要记下root在哪里就好了
询问的时候分类讨论：
1：root == x 直接返回全树最大值就好了
2：lca（root， x） ！= x，那就和x没什么关系了，只要返回原子树最大值就好了
3：lca（root， x） == x，说明x在root的上方，那么找到x的儿子中root的祖先y，除了y的子树就都是x的子树了
跳树链和找lca可以用倍增实现
总复杂度 O(nlog2n)
Code（写的很长……）：
#include <cstdio> using namespace std; const int N = 1e5 + 5; const int Lg = 20; const int inf = 1 << 30; int n, qn, a[N], tot = 0, head[N], root; int dfsc = 0, id[N], siz[N], top[N]; int w[N], dep[N], fa[N][Lg], son[N]; struct Edge { int to, nxt; } e[N << 1]; inline void add(int from, int to) { e[++tot].to = to; e[tot].nxt = head[from]; head[from] = tot; } inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } inline int min(int x, int y) { return x > y ? y : x; } inline void chkMin(int &x, int y) { if(y < x) x = y; } inline void swap(int &x, int &y) { int t = x; x = y; y = t; } void dfs1(int x, int fat, int depth) { siz[x] = 1, fa[x][0] = fat, dep[x] = depth; for(int i = 1; i <= 18; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1]; int maxson = -1; for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; if(y == fat) continue; dfs1(y, x, depth + 1); siz[x] += siz[y]; if(siz[y] > maxson) maxson = siz[y], son[x] = y; } } void dfs2(int x, int topf) { w[id[x] = ++dfsc] = a[x], top[x] = topf; if(!son[x]) return; dfs2(son[x], topf); for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; if(y == fa[x][0] || y == son[x]) continue; dfs2(y, y); } } inline int getLca(int x, int y) { if(dep[x] < dep[y]) swap(x, y); for(int i = 18; i >= 0; i--) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i]; if(x == y) return x; for(int i = 18; i >= 0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; return fa[x][0]; } namespace SegT { int s[N << 2], tag[N << 2]; #define lc p << 1 #define rc p << 1 | 1 #define mid ((l + r) >> 1) inline void up(int p) { if(p) s[p] = min(s[lc], s[rc]); } inline void down(int p) { if(tag[p] == inf) return; s[lc] = tag[lc] = s[rc] = tag[rc] = tag[p]; tag[p] = inf; } void build(int p, int l, int r) { tag[p] = inf; if(l == r) { s[p] = w[l]; return; } build(lc, l, mid); build(rc, mid + 1, r); up(p); } void modify(int p, int l, int r, int x, int y, int v) { if(x <= l && y >= r) { s[p] = tag[p] = v; return; } down(p); if(x <= mid) modify(lc, l, mid, x, y, v); if(y > mid) modify(rc, mid + 1, r, x, y, v); up(p); } int query(int p, int l, int r, int x, int y) { if(x <= l && y >= r) return s[p]; down(p); int res = inf; if(x <= mid) chkMin(res, query(lc, l, mid, x, y)); if(y > mid) chkMin(res, query(rc, mid + 1, r, x, y)); return res; } } using namespace SegT; inline void mtree(int x, int y, int v) { for(; top[x] != top[y]; ) { if(dep[top[x]] < dep[top[y]]) swap(x, y); modify(1, 1, n, id[top[x]], id[x], v); x = fa[top[x]][0]; } if(dep[x] > dep[y]) swap(x, y); modify(1, 1, n, id[x], id[y], v); } inline int ask(int x) { if(root == x) return s[1]; int y = getLca(x, root); if(y == x) { int z = root; for(int i = 18; i >= 0; i--) if(dep[fa[z][i]] > dep[y]) z = fa[z][i]; return min(query(1, 1, n, 1, id[z] - 1), query(1, 1, n, id[z] + siz[z], n)); } else return query(1, 1, n, id[x], id[x] + siz[x] - 1); } int main() { read(n), read(qn); for(int x, y, i = 1; i < n; i++) { read(x), read(y); add(x, y), add(y, x); } dfs1(1, 0, 1); for(int i = 1; i <= n; i++) read(a[i]); dfs2(1, 1); build(1, 1, n); read(root); for(int op; qn--; ) { read(op); if(op == 1) read(root); if(op == 2) { int x, y, v; read(x), read(y), read(v); mtree(x, y, v); } if(op == 3) { int x; read(x); printf("%d ", ask(x)); } } return 0; }