$SATT$是一种用$splay$维护树收缩结构从可以实现树链/子树修改/查询的动态树。
时间复杂度超大常数均摊$O(logn)$。
研究了两天，参考了别人的代码和博客，但是现在也没理解透彻原理。
有一些压行，代码比较丑。

#include <iostream>

using namespace std;

const int N = 500010;
const int inf = 1e9;

#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]
#define ms(x) tr[x].s[2]
#define fa(x) tr[x].fa

struct Tag {
    int mul, add;
    Tag(int mul = 1, int add = 0) : mul(mul), add(add) {}
    void clear() { mul = 1, add = 0; }
};

struct Data {
    int sz, sum, mx, mn;
    Data(int sz = 0, int sum = 0, int mx = -inf, int mn = inf) : sz(sz), sum(sum), mx(mx), mn(mn) {}
};

Tag operator+ (Tag& a, Tag& b) { return Tag(a.mul * b.mul, a.add * b.mul + b.add); }
Data operator+ (const Data& a, const Data& b) { return Data(a.sz + b.sz, a.sum + b.sum, max(a.mx, b.mx), min(a.mn, b.mn)); }
Data operator+ (const Data& a, const Tag& b) { return Data(a.sz, a.sum * b.mul + a.sz * b.add, a.mx == -inf ? -inf : a.mx * b.mul + b.add, a.mn == inf ? inf : a.mn * b.mul + b.add); }
int operator+ (const int& a, const Tag& b) { return a * b.mul + b.add; }

struct Node {
    int v, fa, s[3];
    int rev;
    Tag pt, tt;
    /* path tag & tree tag */
    Data p, t;
    void clear() {
        tt.clear(), pt.clear();
        v = rev = s[0] = s[1] = s[2] = 0;
    }
} tr[N];
int stk[N], top, idx;
int root;
pair<int, int> edge[N];
int n, m;

void clear(int& x) { tr[x].clear(), stk[++top] = x; }
int new_node() { return top ? stk[top--] : ++idx; }
bool get(int x) { return x == rs(fa(x)); }
bool isroot(int x) { return ls(fa(x)) != x && rs(fa(x)) != x; }
void set(int x, int fa, int t) { if (x) fa(x) = fa; tr[fa].s[t] = x; }
void rev(int x) { swap(ls(x), rs(x)), tr[x].rev ^= 1; }

void pathtag(int x, Tag& tag) {
    tr[x].v = tr[x].v + tag;
    tr[x].p = tr[x].p + tag;
    tr[x].pt = tr[x].pt + tag;
}

void treetag(int x, Tag& tag) {
    tr[x].t = tr[x].t + tag;
    tr[x].tt = tr[x].tt + tag;
}

void pushup(int x, int t) {
    auto& u = tr[x], &l = tr[ls(x)], &r = tr[rs(x)], &m = tr[ms(x)];
    if (!t) {
        /* compress node */
        u.t = l.t + m.t + r.t;
        u.p = l.p + Data(1, u.v, u.v, u.v) + r.p;
    } else {
        /* rake node */
        u.t = l.t + m.t + m.p + r.t;
    }
}

void pushdown(int x, int t) {
    if (!t) {
        /* compress node */  
        if (tr[x].rev) {
            rev(ls(x)), rev(rs(x));
            tr[x].rev = 0; 
        }
        if (tr[x].pt.mul != 1 || tr[x].pt.add) {
            pathtag(ls(x), tr[x].pt);
            pathtag(rs(x), tr[x].pt);
            tr[x].pt.clear();
        }
        if (tr[x].tt.mul != 1 || tr[x].tt.add) {
            treetag(ls(x), tr[x].tt);
            treetag(rs(x), tr[x].tt);
            treetag(ms(x), tr[x].tt);
            tr[x].tt.clear();
        }
    } else {
        /* rake node */
        if (tr[x].tt.mul != 1 || tr[x].tt.add) {
            treetag(ls(x), tr[x].tt);
            treetag(rs(x), tr[x].tt);
            treetag(ms(x), tr[x].tt);
            pathtag(ms(x), tr[x].tt);
            tr[x].tt.clear();
        }
    }
}

void pushall(int x, int t) {
    if (!isroot(x)) pushall(fa(x), t);
    pushdown(x, t);
}

void rotate(int x, int t) {
    int y = fa(x), z = fa(y);
    int k = get(x), w = tr[x].s[k ^ 1]; 
    if (z) tr[z].s[ms(z) == y ? 2 : get(y)] = x;
    if (w) fa(w) = y;
    fa(x) = z, tr[x].s[k ^ 1] = y;
    fa(y) = x, tr[y].s[k] = w;
    pushup(y, t), pushup(x, t);
}

void splay(int x, int t, int goal = 0) {
    pushall(x, t);
    for (int y; y = fa(x), !isroot(x) && y != goal; rotate(x, t))
        if (fa(y) != goal && !isroot(y)) 
            rotate(get(x) == get(y) ? y : x, t);
}

void del(int x) {
    set(ms(x), fa(x), 1);
    if (ls(x)) {
        int y = ls(x);
        pushdown(y, 1);
        for (pushdown(y, 1); rs(y); y = rs(y)) pushdown(y, 1);
        splay(y, 1, x);
        set(rs(x), y, 1);
        set(y, fa(x), 2);
        pushup(y, 1), pushup(fa(x), 0);
    } else {
        set(rs(x), fa(x), 2);
    } 
    clear(x);
}

void splice(int x) {
    /*  local splay */  
    splay(x, 1);
    int y = fa(x);
    splay(y, 0);
    pushdown(x, 1);
    /*  splice  */
    if (rs(y)) swap(fa(ms(x)), fa(rs(y))), swap(ms(x), rs(y));
    else del(x);
    pushup(x, 1), pushup(y, 0);
}

void access(int x) {
    splay(x, 0);
    int z = x;
    if (rs(x)) {
        int y = new_node();
        set(ms(x), y, 0);
        set(rs(x), y, 2);
        rs(x) = 0;
        set(y, x, 2);
        pushup(y, 1);
        pushup(x, 0);
    }
    while (fa(x)) splice(fa(x)), x = fa(x), pushup(x, 0);   
    splay(z, 0);
    /* global splay */
}

void evert(int x) { access(x), rev(x); } /* aka. makeroot */
void expose(int x, int y) { evert(x), access(y); } /* aka. split */
void link(int x, int y) { access(x), evert(y), set(y, x, 1), pushup(x, 0); }
void change_root(int x) { evert(root = x); }
int findroot(int x) { access(x); while (ls(x)) pushdown(x, 0), x = ls(x); splay(x, 0); return x; }
int cut(int x) { access(x); int y = ls(x); for (; rs(y); y = rs(y)) pushdown(y, 0); ls(x) = fa(ls(x)) = 0; pushup(x, 0); return y; }
Data path_query(int x, int y) { expose(x, y); Data res = tr[y].p; evert(root); return res; }
Data tree_query(int x) { access(x); Data res = Data(1, tr[x].v, tr[x].v, tr[x].v) + tr[ms(x)].t; return res; }

void path_update(int x, int y, int mul, int add) { 
    Tag tag(mul, add); 
    expose(x, y);
    pathtag(y, tag);
    evert(root); 
}

void tree_update(int x, int mul, int add) { 
    Tag tag(mul, add); 
    access(x);
    treetag(ms(x), tag);
    tr[x].v = tr[x].v + tag;
    pushup(x, 0);
    evert(root); 
}

void change_father(int x, int y) {
    if (x == y || x == root) return;
    int z = cut(x);
    if (findroot(x) == findroot(y)) link(x, z);
    else link(x, y);
    evert(root);
}

int main() {
    Data tmp(0, 0, -inf, inf);
    tr[0].t = tr[0].p = tmp;
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        auto& [u, v] = edge[i];
        cin >> u >> v;
    }
    for (int i = 1; i <= n; i++) {
        cin >> tr[i].v;
        pushup(i, 0);
    }
    idx = n;
    for (int i = 1; i < n; i++) {
        auto& [u, v] = edge[i];
        link(u, v);
    }    
    cin >> root;
    evert(root);
    while (m--) {
        int op, x, y, z;
        cin >> op;
        /* subtree update */
        if (op == 0 || op == 5) {
            cin >> x >> y;
            if (op == 0) tree_update(x, 0, y);
            if (op == 5) tree_update(x, 1, y);
        }
        /* path update */
        if (op == 2 || op == 6) {
            cin >> x >> y >> z;
            if (op == 2) path_update(x, y, 0, z);
            if (op == 6) path_update(x, y, 1, z);
        } 
        /* subtree query */
        if (op == 3 || op == 4 || op == 11) {
            cin >> x;
            Data data = tree_query(x);
            if (op == 3) cout << data.mn << '\n';
            if (op == 4) cout << data.mx << '\n';
            if (op == 11) cout << data.sum << '\n';
        }
        /* path query */
        if (op == 7 || op == 8 || op == 10) {
            cin >> x >> y;
            Data data = path_query(x, y);
            if (op == 7) cout << data.mn << '\n';
            if (op == 8) cout << data.mx << '\n';
            if (op == 10) cout << data.sum << '\n';
        }
        /* change root */
        if (op == 1) {
            cin >> x;
            change_root(x);
        }
        /* change structure */
        if (op == 9) {
            cin >> x >> y;
            change_father(x, y);
        }
    }
    return 0;
}