LCT 90 pts 求条玄关

#include <bits/stdc++.h>

#define int long long

using namespace std;

namespace zcq_qwq {
    const int N = 1e5 + 5, inf = 0x3f3f3f3f3f3f3f3f;

    class LCT {
public : 
        struct node {
            int son[2];
            int fa, tag, ass, mn, val;
            multiset<int> s;
        } tree[N];
        void pushup(int x) {tree[x].mn = min({tree[tree[x].son[0]].mn, tree[tree[x].son[1]].mn, tree[x].val}); if (!tree[x].s.empty()) tree[x].mn = min(tree[x].mn, *tree[x].s.begin());}
        bool isroot(int x) {return tree[tree[x].fa].son[0] != x && tree[tree[x].fa].son[1] != x;}
        bool get(int x) {return tree[tree[x].fa].son[1] == x;}
        void rotate(int x) {
            int y = tree[x].fa, z = tree[y].fa, d = get(x);
            if (!isroot(y)) tree[z].son[get(y)] = x;
            tree[tree[x].son[!d]].fa = y, tree[y].son[d] = tree[x].son[!d];
            tree[x].son[!d] = y, tree[y].fa = x, tree[x].fa = z, pushup(y), pushup(x);
        }
        void pushdown(int x) {
            if (tree[x].tag) {tree[tree[x].son[0]].tag ^= 1, tree[tree[x].son[1]].tag ^= 1, swap(tree[x].son[0], tree[x].son[1]), tree[x].tag = 0;}
            if (tree[x].ass != inf) {
                tree[tree[x].son[0]].val = tree[tree[x].son[0]].ass = tree[x].ass;
                tree[tree[x].son[1]].val = tree[tree[x].son[1]].ass = tree[x].ass;
                tree[x].ass = inf;
                // pushup(tree[x].son[0]);
                // pushup(tree[x].son[1]);
            }
        }
        void update(int x) {if (!isroot(x)) {update(tree[x].fa);} pushdown(x);}
        void splay(int x) {update(x); for (int f = tree[x].fa; !isroot(x); rotate(x), f = tree[x].fa) {if (!isroot(f)) rotate(get(f) == get(x) ? f : x);} pushup(x);}
        void access(int x) {
            for (int f = 0; x; f = x, x = tree[x].fa) {
                splay(x);
                if (tree[x].son[1]) tree[x].s.insert(tree[tree[x].son[1]].mn);
                if (f) {auto it = tree[x].s.find(tree[f].mn); if (it != tree[x].s.end()) {tree[x].s.erase(it);}}
                tree[x].son[1] = f, pushup(x);
            }
        }
        void makeroot(int x) {access(x), splay(x), tree[x].tag ^= 1;}
        void link(int x, int y) {makeroot(x), access(y), splay(y), tree[x].fa = y, tree[y].s.insert(tree[x].mn), pushup(y);}
    } lct;

    int n, m;

    void main() {
        cin >> n >> m;
        for (int i = 0; i <= n; i++) {lct.tree[i].ass = inf, lct.tree[i].mn = lct.tree[i].val = inf;}
        for (int i = 1; i < n; i++) {
            int u, v; cin >> u >> v;
            lct.link(u, v);
        }
        for (int i = 1; i <= n; i++) {
            int x; cin >> x;
            lct.access(i), lct.splay(i), lct.tree[i].val = x, lct.pushup(i);
        }
        int root;
        cin >> root;
        lct.makeroot(root);
        for (int i = 1; i <= m; i++) {
            int opt, x, y, z; cin >> opt >> x;
            if (opt == 1) {lct.makeroot(x); root = x;} else if (opt == 2) {
                cin >> y >> z;
                lct.makeroot(x), lct.access(y), lct.splay(y), lct.tree[y].ass = lct.tree[y].val = z, lct.pushup(y), lct.pushdown(y), lct.makeroot(root);
            } else {lct.access(x), lct.splay(x); if (lct.tree[x].s.empty()) {cout << lct.tree[x].val << endl;} else {cout << min(lct.tree[x].val, *lct.tree[x].s.begin()) << endl;}}
        }
    }
}

signed main() {
    zcq_qwq::main(); return 0;
}