题面

解法

如果没有换根，就是树剖+线段树的板子题

如果有换根，看当前的根是否为\(x\)的后代，如果不是，那么\(x\)的子树不会受到任何影响，如果是，那么直接删除对应区间然后求最小值即可

时间复杂度：\(O(q\ log^2\ n)\)

代码

#include 
    
     #define N 100010using namespace std;template 
     
       void read(node &x) {    x = 0; int f = 1; char c = getchar();    while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}    while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;}int n, m, cnt, Time;int a[N], d[N], f[N], siz[N], son[N], dfn[N], top[N], Real[N], g[N][21];struct Edge {    int next, num;} e[N * 3];struct SegmentTree {    struct Node {        int l, r, fl, minv;    } t[N * 4];    void update(int k) {        t[k].minv = min(t[k << 1].minv, t[k << 1 | 1].minv);    }    void build(int k, int l, int r) {        t[k] = (Node) {l, r, 0, INT_MAX};        if (l == r) {t[k].minv = a[Real[l]]; return;}        int mid = (l + r) >> 1;        build(k << 1, l, mid);        build(k << 1 | 1, mid + 1, r);        update(k);    }    void pushdown(int k) {        int x = t[k].fl; t[k].fl = 0;        int ls = k << 1, rs = k << 1 | 1;        t[ls].fl = t[ls].minv = t[rs].fl = t[rs].minv = x;    }    void modify(int k, int L, int R, int v) {        int l = t[k].l, r = t[k].r;        if (L <= l && r <= R) {            t[k].fl = t[k].minv = v;            return;        }        if (t[k].fl) pushdown(k);        int mid = (l + r) >> 1;        if (L <= mid && mid < R)            modify(k << 1, L, mid, v), modify(k << 1 | 1, mid + 1, R, v);        if (R <= mid) modify(k << 1, L, R, v);        if (L > mid) modify(k << 1 | 1, L, R, v);        update(k);    }    int query(int k, int L, int R) {        if (L > R) return INT_MAX;        int l = t[k].l, r = t[k].r;        if (L <= l && r <= R) return t[k].minv;        if (t[k].fl) pushdown(k);        int mid = (l + r) >> 1;        if (R <= mid) return query(k << 1, L, R);        if (L > mid) return query(k << 1 | 1, L, R);        return min(query(k << 1, L, mid), query(k << 1 | 1, mid + 1, R));    }} T;void add(int x, int y) {    e[++cnt] = (Edge) {e[x].next, y};    e[x].next = cnt;}void dfs1(int x, int fa) {    d[x] = d[fa] + 1, siz[x] = 1, f[x] = fa;    for (int i = 1; i <= 20; i++)        g[x][i] = g[g[x][i - 1]][i - 1];    for (int p = e[x].next; p; p = e[p].next) {        int k = e[p].num;        if (k == fa) continue; g[k][0] = x;        dfs1(k, x); siz[x] += siz[k];        if (siz[son[x]] < siz[k]) son[x] = k;    }}void dfs2(int x, int tp) {    top[x] = tp, dfn[x] = ++Time, Real[Time] = x;    if (!son[x]) return; dfs2(son[x], tp);    for (int p = e[x].next; p; p = e[p].next) {        int k = e[p].num;        if (k == f[x] || k == son[x]) continue;        dfs2(k, k);    }}void Modify(int x, int y, int v) {    int fx = top[x], fy = top[y];    while (fx != fy) {        if (d[fx] < d[fy]) swap(x, y), swap(fx, fy);        T.modify(1, dfn[fx], dfn[x], v);        x = f[fx], fx = top[x];    }    if (d[x] > d[y]) swap(x, y);    T.modify(1, dfn[x], dfn[y], v);}int calc(int x, int y) {    for (int i = 20; i >= 0; i--)        if (d[g[x][i]] - d[y] >= 1) x = g[x][i];    return x;}int solve(int l, int r, int L, int R) {    return min(T.query(1, l, L - 1), T.query(1, R + 1, r));}main() {    read(n), read(m); cnt = n;    for (int i = 1; i < n; i++) {        int x, y; read(x), read(y);        add(x, y), add(y, x);    }    for (int i = 1; i <= n; i++) read(a[i]);    int rt; read(rt);    dfs1(rt, 0), dfs2(rt, 0);    T.build(1, 1, n);    while (m--) {        int opt; read(opt);        if (opt == 1) read(rt);        if (opt == 2) {            int x, y, v; read(x), read(y), read(v);            Modify(x, y, v);        }        if (opt == 3) {            int x; read(x);            if (x == rt) {cout << T.query(1, 1, n) << "\n"; continue;}            if (dfn[rt] < dfn[x] || dfn[rt] > dfn[x] + siz[x] - 1 || (dfn[rt] <= dfn[x] && dfn[x] + siz[x] - 1 <= dfn[rt] + siz[rt] - 1)) {                cout << T.query(1, dfn[x], dfn[x] + siz[x] - 1) << "\n";                continue;            }            int t = calc(rt, x), ans = solve(1, n, dfn[t], dfn[t] + siz[t] - 1);            cout << ans << "\n";        }    }    return 0;}