P3979 遥远的国度 LCT维护子树信息

Genius_Z · 2019-03-25 18:59:21 · 题解

做完这题想必会对LCT有一个新的认识吧。

曾经有人说过树剖能做的题LCT都能做（虽然可能会很麻烦）

先看这题的操作：

• 换根
• 链修改
• 子树求最小值

若没有3操作显然优先考虑LCT。

那如何处理3操作呢

我们考虑分开处理子树与链的贡献，记子树的最小值为ts，链的最小值为tc

那么显然min(ts,tc)即为所求

链的最小值非常好处理，就是LCT的板子，不多加赘述了

主要考虑子树的贡献

考虑与每个节点相连的边，不是实边就是虚边，实边的信息由链处理了。

那么我们要考虑的只有虚边，由记录虚子树的做法，我们可以联想到用某种东西维护虚子树

支持插入，删除，维护最小值的数据结构，当然是平衡树了

这里偷懒使用了multiset（第一遍splay写挂了，写了200+行，又丑又长）

注意本题最大的细节就在于对于根的处理，由于链修改会换根，所以需要在链修改后把根换回来

用一个变量记录当前的根，每次操作后makeroot

code：（码风应该还算正常）

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inl inline
#define re register int
#define lowbit(x) ((x) & (-x))
#define ll long long
#define ls(x) t[x].child[0]
#define rs(x) t[x].child[1]
#define fa(x) t[x].fa
const int inf = 0x7fffffff;
using namespace std;
template < class Read >
inl Read read() {
    Read x = 0;
    register bool w = 0;
    register char c = getchar();
    while (c > '9' || c < '0') {
        if (c == '-') w = 1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return w ? -x : x;
}
struct node {
    int child[2], fa, w, tot, tc, ts;
    bool filp, modify;
    multiset<int>s;
} t[200001];
bool vis[200001];
inl void upd(int x) {
    t[x].tc = t[x].tot = t[x].w, t[x].ts = inf;
    t[x].tc = min(min(t[ls(x)].tc, t[rs(x)].tc), t[x].tc);//链
    t[x].ts = min(min(t[ls(x)].ts, t[rs(x)].ts), *t[x].s.begin());//子树
    t[x].tot = min(t[x].tc, t[x].ts);
}
inl void reverse(int x) {
    swap(ls(x), rs(x));
    t[x].filp ^= 1;
}
inl void change(int x, int w) {
    if (!x)return;
    t[x].tc = t[x].w = w, t[x].modify = 1, t[x].tot = min(t[x].tc, t[x].ts);
}
inl void pushdown(int x) {
    //注意这里的修改不能清空filp标记，因为这里的filp并不是链翻转
    if (t[x].modify) {
        if (ls(x))change(ls(x), t[x].w);
        if (rs(x))change(rs(x), t[x].w);
        t[x].modify = 0;
    }
    if (t[x].filp) {
        if (ls(x))reverse(ls(x));
        if (rs(x))reverse(rs(x));
        t[x].filp = 0;
    }
}
inl bool poi(int x) {
    return rs(fa(x)) == x;
}
inl bool nroot(int x) {
    return ls(fa(x)) == x || rs(fa(x)) == x;
}
inl void rotate(int x) {
    int f = fa(x), gf = fa(f);
    bool fs = poi(x), gfs = poi(f);
    int s = t[x].child[fs ^ 1];
    if (nroot(f))t[gf].child[gfs] = x;
    t[f].child[fs] = s, t[x].child[fs ^ 1] = f;
    fa(x) = gf, fa(f) = x;
    if (s)fa(s) = f;
    upd(f);
}
inl void push(int x) {
    if (nroot(x))push(fa(x));
    pushdown(x);
}
inl void splay(int x) {
    push(x);
    while (nroot(x)) {
        if (nroot(fa(x)))poi(x) == poi(fa(x)) ? rotate(fa(x)) : rotate(x);
        rotate(x);
    }
    upd(x);
}
inl void access(int x) {
    for (re i = 0; x; x = t[i = x].fa) {
        splay(x);
        if (i) t[x].s.erase(t[x].s.lower_bound(t[i].tot));
        if (rs(x))t[x].s.insert(t[rs(x)].tot);
        rs(x) = i, upd(x);
    }
}
inl void makeroot(int x) {
    access(x), splay(x), reverse(x);
}
inl void split(int x, int y) {
    makeroot(y), access(x), splay(x);
}
struct edge {
    int next, to;
}e[5000001];
int tot, head[5000001];
inl void add(int x, int y) {
    e[++tot] = edge{ head[x],y }, head[x] = tot;
}
void dfs(int x, int fa) {
    t[x].s.insert(inf);
    t[x].fa = fa;
    for (re i = head[x]; i; i = e[i].next) {
        if (e[i].to != fa) {
            dfs(e[i].to, x);
            t[x].s.insert(t[e[i].to].tot);
        }
    }
    upd(x);
}
signed main() {
    t[0].tc = t[0].ts = t[0].tot = inf;
    t[0].s.insert(inf);//由于0节点是每个节点初始时的儿子，为了少加几句if所以直接赋值成inf;
    re n = read<int>(), m = read<int>(), x, y, w, root, op;
    for (re i = 1; i < n; i++) {
        x = read<int>(), y = read<int>();
        add(x, y), add(y, x);
    }
    for (re i = 1; i <= n; i++)t[x].tot = t[x].tc = t[i].w = read<int>(), t[x].ts = inf;//初始化
    root = read<int>();
    dfs(root, 0);
    makeroot(root);
    while (m--) {
        op = read<int>();
        if (op == 1) {
            makeroot(root = read<int>());
        }
        else if (op == 2) {
            x = read<int>(), y = read<int>(), w = read<int>();
            split(x, y), change(x, w), makeroot(root);
        }
        else {
            x = read<int>();
            access(x), splay(x), printf("%d\n", min(t[x].w, *t[x].s.begin()));
        }
    }
}