P3833 魔法树 LCT维护子树信息

Genius_Z · 2019-04-19 13:35:04 · 题解

讲一下如何用LCT维护子树信息

众所周知，LCT强在维护链信息而弱在维护子树信息

但是维护子树信息也是可以做的，这样可以应对一些出题人比较毒瘤的情况（比如又加边删边还查询子树）

定义vir为某个节点虚子树的权值和，tot为总权值和。

当access导致虚实转换时，vir就要加上当前实儿子（将要成为虚儿子）的tot，减去将要成为实儿子的tot

这题因为初始没有点权，所以不需要在link的时候加上虚子树的值，但我这里为了指出在有权时的做法加上了。

还有就是注意有根树每次查找要makeroot原树的根。

Code：

#include <algorithm>
#include <tuple>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define inl inline
#define re register int
#define fa(x) t[x].fa
#define ls(x) t[x].child[0]
#define rs(x) t[x].child[1]
#define int long long
const int inf = 0x3f3f3f3f;
#define lowbit(x) ((x) & (-x))
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 tot, vir, w, fa, child[2], tag, size;
    bool filp;
} t[100001];
inl void maintain(int x) {
    t[x].tot = t[x].vir + t[x].w + t[ls(x)].tot + t[rs(x)].tot;
    t[x].size = t[ls(x)].size + t[rs(x)].size + 1;
}
inl bool nroot(int x) {
    return ls(fa(x)) == x || rs(fa(x)) == x;
}
inl bool poi(int x) {
    return rs(fa(x)) == x;
}
inl void rotate(int x) {
    re f = fa(x), gf = fa(f), fs = poi(x), gfs = poi(f), 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;
    if (s) fa(s) = f;
    fa(f) = x, fa(x) = gf;
    maintain(f);
}
inl void reverse(int x) {
    swap(ls(x), rs(x));
    t[x].filp ^= 1;
}
inl void sum(int x, int w) {
    t[x].tag += w, t[x].tot += w * t[x].size, t[x].w += w;
}
inl void pushdown(int x) {
    if (t[x].filp) {
        if (ls(x)) reverse(ls(x));
        if (rs(x)) reverse(rs(x));
        t[x].filp = 0;
    }
    if (t[x].tag) {
        if (ls(x)) sum(ls(x), t[x].tag);
        if (rs(x)) sum(rs(x), t[x].tag);
        t[x].tag = 0;
    }
}
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(fa(x)) == poi(x) ? rotate(fa(x)) : rotate(x);
        rotate(x);
    }
    maintain(x);
}
inl void access(int x) {
    for (re i = 0; x; x = fa(i = x)) {
        splay(x), t[x].vir += t[rs(x)].tot, t[x].vir -= t[rs(x) = i].tot, maintain(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);
}
inl void link(int x, int y) {
    split(x, y), fa(y) = x, t[x].vir += t[y].w;
}
inl bool spread() {
    register char c = getchar();
    while (c != 'A' && c != 'Q')
        c = getchar();
    return c == 'Q';
}
signed main() {
    re n = read<int>();
    for (re i = 1; i < n; i++) {
        re x = read<int>() + 1, y = read<int>() + 1;
        link(x, y);
    }
    re m = read<int>();
    while (m--) {
        re op = spread(), x = read<int>() + 1;
        if (!op) {
            re y = read<int>() + 1, w = read<int>();
            split(x, y), sum(x, w);
        }
        else {
            makeroot(1), access(x), splay(x);
            printf("%lld\n", t[x].tot - t[ls(x)].tot);
        }
    }
}