这个世界就是一棵巨大的 SATT

251Sec · 2024-08-24 16:02:26 · 题解

记录下我对 SATT 的理解。不知道对不对，欢迎指正。

首先我们考虑下静态 Top Tree 是在干啥，它实际上描述了一个链分治的过程，即每次选择一条重链，把剩下的部分递归分解，然后分治把轻儿子合并到重边上（对应 Rake Tree），再分治合并重链。（对应 Compress Tree）

接下来我们把原本静态 Top Tree 的结构用一棵三叉树的结构替代。其中每个 Compress 节点只考虑左右儿子得到的部分仍然描述重链的分治树，而中儿子则挂上一棵 Rake Tree，代表最后把这棵 Rake Tree 合并（Rake）到这个 Compress 节点上。对于 Rake 节点，它的左右儿子仍然描述分治 Rake 的过程，中儿子挂上一棵 Compress Tree，代表把左右儿子 Rake 到中儿子上。

在保持中儿子不变的情况下，实际上不管是 Rake Tree 还是 Compress Tree 我们都只关心它的左右儿子的中序遍历而非树的具体形态，这意味着它是支持旋转的。注意基簇不能转，但是这里我们维护点的信息而非边的信息，实际上省略了基簇的部分，并把点的信息放在它对应的 Compress 节点上加入。这一结构看起来非常像是平衡树维护轻儿子的 LCT（或者 AAAT？）：一条实链被一棵 Compress Tree 维护，然后轻儿子被 Rake Tree 挂在下面。

考虑核心操作 Access 的实现，它干的事情是把一个点 x 到根的路径打通成实链，这表现为它和根节点成为根簇的端点。

• 先让 x 成为它所在簇的端点，这可以通过把它 Splay 到所在 Compress Tree 的根再把它的右儿子和中儿子挂在它的中儿子的 Rake Tree 上实现。
• 接下来，我们需要反复打通某个点 x 到父亲的边。记它的父亲为 u，则我们把 u（一定是 Rake 节点）旋到它所在 Rake Tree 根之后它的父亲 v 是一个 Compress 节点，我们希望让 x 成为 v 的实儿子。如果 v 有右儿子，那么把它和 x 交换就好了。否则我们需要把 x 先挂到 v 的右儿子上，然后发现 u 失去了中儿子，作为 Rake 节点已经不合法，则我们需要把 u 的左右子树做 Splay 合并然后删去 u。

实现 Access 操作之后剩下的事情就很简单了。

复杂度证明不会。实现参考了 OI-wiki。

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
struct Tag {
    int k, b;
    Tag() { k = 1, b = 0; }
    Tag(int k, int b) : k(k), b(b) {}
    bool NE() { return k != 1 || b != 0; } 
};
struct Dat {
    int siz, min, max, sum;
    Dat() { siz = 0, min = inf, max = -inf, sum = 0; }
    Dat(int siz, int min, int max, int sum) : siz(siz), min(min), max(max), sum(sum) {}
};
Tag operator+(const Tag &x, const Tag &y) { return { x.k * y.k, x.b * y.k + y.b }; }
Dat operator+(const Dat &x, const Dat &y) { return { x.siz + y.siz, min(x.min, y.min), max(x.max, y.max), x.sum + y.sum }; }
Dat operator+(const Dat &x, const Tag &y) { return { x.siz, x.min == inf ? inf : x.min * y.k + y.b, x.max == -inf ? -inf : x.max * y.k + y.b, x.sum * y.k + x.siz * y.b }; }
int operator+(int x, const Tag &y) { return x * y.k + y.b; }
struct Node {
    int val, fa, ch[3];
    bool rev;
    Tag pTg, sTg;
    Dat pat, sub;
    void Clear() {
        pTg = sTg = Tag();
        pat = sub = Dat();
        val = rev = fa = ch[0] = ch[1] = ch[2] = 0;
    }
} f[500005];
int &ls(int x) { return f[x].ch[0]; }
int &ms(int x) { return f[x].ch[2]; }
int &rs(int x) { return f[x].ch[1]; }
int &fa(int x) { return f[x].fa; }
int st[500005], top, cnt;
void Clear(int x) { f[x].Clear(), st[++top] = x; }
int NewNode() { return top ? st[top--] : ++cnt; }
bool Dir(int x) { return x == rs(fa(x)); }
bool IsRt(int x) { return ls(fa(x)) != x && rs(fa(x)) != x; }
void Set(int x, int fx, int t) { if (x) fa(x) = fx; f[fx].ch[t] = x; }
void Rev(int x) { swap(ls(x), rs(x)), f[x].rev ^= 1; }
void PathTag(int x, Tag w) {
    f[x].val = f[x].val + w;
    f[x].pTg = f[x].pTg + w;
    f[x].pat = f[x].pat + w;
}
void SubTag(int x, Tag w) {
    f[x].sTg = f[x].sTg + w;
    f[x].sub = f[x].sub + w;
}
void Pushdown(int x, int t) {
    if (!t) {
        if (f[x].rev) {
            Rev(ls(x)), Rev(rs(x));
            f[x].rev = 0;
        }
        if (f[x].pTg.NE()) {
            PathTag(ls(x), f[x].pTg), PathTag(rs(x), f[x].pTg);
            f[x].pTg = Tag();
        }
        if (f[x].sTg.NE()) {
            SubTag(ls(x), f[x].sTg), SubTag(ms(x), f[x].sTg), SubTag(rs(x), f[x].sTg);
            f[x].sTg = Tag();
        }
    }
    else {
        if (f[x].sTg.NE()) {
            SubTag(ls(x), f[x].sTg), SubTag(ms(x), f[x].sTg), SubTag(rs(x), f[x].sTg);
            PathTag(ms(x), f[x].sTg);
            f[x].sTg = Tag();
        }
    }
}
void Pushup(int x, int t) {
    if (!t) {
        f[x].pat = f[ls(x)].pat + Dat(1, f[x].val, f[x].val, f[x].val) + f[rs(x)].pat;
        f[x].sub = f[ls(x)].sub + f[rs(x)].sub + f[ms(x)].sub;
    }
    else {
        f[x].sub = f[ls(x)].sub + f[rs(x)].sub + f[ms(x)].sub + f[ms(x)].pat;
    }
}
void Upd(int x, int t) {
    if (!IsRt(x)) Upd(fa(x), t);
    Pushdown(x, t);
}
void Rot(int x, int t) {
    int y = fa(x), z = fa(y), d = Dir(x), w = f[x].ch[!d];
    if (z) f[z].ch[ms(z) == y ? 2 : Dir(y)] = x;
    if (w) fa(w) = y;
    fa(x) = z, f[x].ch[!d] = y;
    fa(y) = x, f[y].ch[d] = w;
    Pushup(y, t), Pushup(x, t);
}
void Splay(int x, int t, int tar = 0) {
    Upd(x, t);
    for (int y; y = fa(x), !IsRt(x) && y != tar; Rot(x, t)) {
        if (fa(y) != tar && !IsRt(y)) Rot(Dir(y) == Dir(x) ? y : x, t); 
    }
}
void Del(int x) {
    Set(ms(x), fa(x), 1);
    if (ls(x)) {
        int y = ls(x);
        Pushdown(y, 1);
        while (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) {
    Splay(x, 1); int y = fa(x); Splay(y, 0);
    Pushdown(x, 1);
    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 = NewNode();
        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);
}
int rt;
void MakeRt(int x) { Access(x), Rev(x); }
void ChgRt(int x) { MakeRt(rt = x); }
void Expose(int x, int y) { MakeRt(x), Access(y); }
void Link(int x, int y) { Access(x), MakeRt(y), Set(y, x, 1), Pushup(x, 0); }
int Cut(int x) {
    Access(x);
    int y = ls(x);
    while (rs(y)) Pushdown(y, 0), y = rs(y);
    ls(x) = fa(ls(x)) = 0;
    Pushup(x, 0);
    return y;
}
int Find(int x) { Access(x); while (ls(x)) Pushdown(x, 0), x = ls(x); Splay(x, 0); return x; }
Dat QPath(int x, int y) {
    Expose(x, y);
    Dat res = f[y].pat;
    MakeRt(rt);
    return res;
}
Dat QSub(int x) {
    Access(x);
    Dat res = f[ms(x)].sub + Dat(1, f[x].val, f[x].val, f[x].val);
    MakeRt(rt);
    return res;
}
void MPath(int x, int y, Tag w) {
    Expose(x, y);
    PathTag(y, w);
    MakeRt(rt);
}
void MSub(int x, Tag w) {
    Access(x);
    SubTag(ms(x), w), f[x].val = f[x].val + w;
    Pushup(x, 0);
    MakeRt(rt);
}
void ChgFa(int x, int y) {
    if (x == y || x == rt) return;
    int z = Cut(x);
    if (Find(x) == Find(y)) Link(x, z);
    else Link(x, y);
    MakeRt(rt);
}
int n, q;
int eu[100005], ev[100005];
int main() {
    scanf("%d%d", &n, &q), cnt = n;
    for (int i = 1; i < n; i++) scanf("%d%d", eu + i, ev + i);
    for (int i = 1, w; i <= n; i++) {
        scanf("%d", &w);
        f[i].val = w;
        Pushup(i, 0);
    }
    for (int i = 1; i < n; i++) Link(eu[i], ev[i]);
    scanf("%d", &rt), ChgRt(rt);
    while (q--) {
        int op; scanf("%d", &op);
        if (op == 0 || op == 5) {
            int x, y; scanf("%d%d", &x, &y);
            Tag w = { op != 0, y };
            MSub(x, w);
        }
        else if (op == 1) {
            int x; scanf("%d", &x);
            ChgRt(x);
        }
        else if (op == 2 || op == 6) {
            int x, y, z; scanf("%d%d%d", &x, &y, &z);
            Tag w = { op != 2, z };
            MPath(x, y, w);
        }
        else if (op == 3 || op == 4 || op == 11) {
            int x; scanf("%d", &x);
            Dat res = QSub(x);
            if (op == 3) printf("%d\n", res.min);
            else if (op == 4) printf("%d\n", res.max);
            else printf("%d\n", res.sum);
        }
        else if (op == 7 || op == 8 || op == 10) {
            int x, y; scanf("%d%d", &x, &y);
            Dat res = QPath(x, y);
            if (op == 7) printf("%d\n", res.min);
            else if (op == 8) printf("%d\n", res.max);
            else printf("%d\n", res.sum);
        }
        else if (op == 9) {
            int x, y; scanf("%d%d", &x, &y);
            ChgFa(x, y);
        }
    }
    return 0;
}