换根问题

例题：P3979 遥远的国度

这是个树上查询子树信息问题。一开始一定会给出一个根，接下来会给出一些换根操作（就是让某个节点作为新的树根），在某个换根操作以后，接下来的操作（就是查询）会按照刚才缓过来的根进行查询。因为不论换根前后，这棵树的整体结构形态不变，变的只是节点与节点之间的父子关系。

但是如果真换根的话（就是每换一次根就重新建一棵树）……显然时间复杂度上不允许。那就搞一些特殊操作。

一开始让1当根（我们存储树的信息都是存储其初始形态）

后来让6当根

经分析可发现，父子关系发生变化的只有从 \(1\) 到 \(6\) 这条链。

设当前的根是 \(cr\)，查询的点是 \(x\)，分三种情况：

1. 如果 \(x == cr\) ，直接输出整个子树。
2. 如果 \(x \ne cr\) 并且 \(in[\ x\ ] \le ln[\ cr\ ], out[\ cr\ ] \le out[\ x\ ]\) ，（ \(in[\ ], out[\ ]\) 是某个节点所管辖的区间），枚举与 \(x\) 相连的儿子节点（因为树的边是双向的，所以一定要把其父亲节点排除），找到某一个子节点 \(y\) ，使得 \(cr\) 在以 \(y\) 为根的子树中，那么 \([\ in[\ y\ ],\ out[\ y\ ]\ ]\) 就是要排除的区间。
3. 如果不是以上两种情况，那么就直接查询 \([\ in[\ x\ ],\ out[\ x\ ]\ ]\) 就可以。

代码如下：

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int f(1), x(0);
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c & 15);
    return x * f;
}

const int maxn(100005);

int rt, opt, n, m, val[maxn], a, b, c;
int head[maxn], nxt[maxn << 1], ver[maxn << 1], tot;

inline void add(int x, int y) {
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

int hson[maxn], siz[maxn], dep[maxn], fa[maxn];
int in[maxn], out[maxn], rin[maxn], cnt, top[maxn];

void dfs1(int x) {
    hson[x] = -1; siz[x] = 1;

    for (int i = head[x]; ~i; i = nxt[i]) {
        int y = ver[i];
        if (dep[y]) continue;

        fa[y] = x;
        dep[y] = dep[x] + 1;
        dfs1(y);

        siz[x] += siz[y];
        if (hson[x] == -1 || siz[y] > siz[hson[x]]) hson[x] = y;
    }
}

void dfs2(int x, int f) {
    top[x] = f;
    in[x] = ++cnt; rin[cnt] = x;

    if (hson[x] == -1) {
        out[x] = cnt;
        return;
    }
    dfs2(hson[x], f);

    for (int i = head[x]; ~i; i = nxt[i]) {
        int y = ver[i];
        if (y != hson[x] && y != fa[x]) dfs2(y, y);
    }

    out[x] = cnt;
}

struct Segtree {
    int l, r;
    int minn, lazy;

    // Segtree() : minn(INT_MAX) {};
} t[maxn << 2];

void pushup(int p) {
    t[p].minn = min(t[p << 1].minn, t[p << 1 | 1].minn);
}

void pushdown(int p) {
    if (t[p].lazy) {
        t[p << 1].lazy = t[p << 1 | 1].lazy = t[p].lazy;
        t[p << 1].minn = t[p << 1 | 1].minn = t[p].lazy;
        t[p].lazy = 0;
    }
}

void build(int p, int l, int r) {
    t[p].l = l; t[p].r = r;
    if (l == r) {
        t[p].minn = val[rin[l]];
        return;
    }

    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
}

void change_interval(int p, int l, int r, int v) {
    if (l <= t[p].l && t[p].r <= r) {
        t[p].lazy = t[p].minn = v;
        return;
    }

    pushdown(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) change_interval(p << 1, l, r, v);
    if (r > mid) change_interval(p << 1 | 1, l, r, v);
    pushup(p);
}

void path_change(int x, int y, int v) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        change_interval(1, in[top[x]], in[x], v);
        x = fa[top[x]];
    }

    if (dep[x] > dep[y]) swap(x, y);
    change_interval(1, in[x], in[y], v);
}

int query_min(int p, int l, int r) {
    if (l <= t[p].l && t[p].r <= r) return t[p].minn;

    pushdown(p);
    int tmp(INT_MAX);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) tmp = min(tmp, query_min(p << 1, l, r));
    if (r > mid) tmp = min(tmp, query_min(p << 1 | 1, l, r));
    return tmp;
}

int main() {
    memset(head, 0xff, sizeof(head));
    
    n = read(), m = read();
    for (int i = 1; i < n; ++i) {
        a = read(), b = read();
        add(a, b); add(b, a);
    }

    for (int i = 1; i <= n; ++i) val[i] = read();

    rt = read(); dep[rt] = 1;

    dfs1(rt); dfs2(rt, rt);

    /* for (int i = 1; i <= n; ++i) {
        printf("in[%d] = %d, out[%d] = %d\n", i, in[i], i, out[i]);
    } */

    build(1, 1, n);

    while (m--) {
        opt = read();

        if (opt == 1) {
            rt = read();
        } else if (opt == 2) {
            a = read(), b = read(), c = read();
            path_change(a, b, c);
        } else if (opt == 3) {
            a = read();

            if (a == rt) {
                printf("%d\n", t[1].minn);
            } else if (in[a] <= in[rt] && out[rt] <= out[a]){
                int lc, rc;

                for (int i = head[a]; ~i; i = nxt[i]) {
                    int y = ver[i];
                    if (y == fa[a]) continue; // 排除父节点

                    if (in[y] <= in[rt] && out[rt] <= out[y]) {
                        lc = in[y]; rc = out[y];
                        break;
                    }
                }
                // std::cout << "lc = " << lc << " rc = " << rc << '\n';

                printf("%d\n", min(query_min(1, 1, lc - 1), query_min(1, rc + 1, n)));
            } else {
                printf("%d\n", query_min(1, in[a], out[a]));
            } 
        }
    }
}