【题解】[SHOI2012] 魔法树 虚子树信息 lct BZOJ – 2836

题目链接

树链剖分模板题，子树的 dfs 序是连续的，因此这题询问用树剖也是一个 $\log$的，修改 $\log _ 2 ^ 2$

然而我是来复习 lct 的，发现自己忘得差不多了

lct 维护一下虚子树和就行了，在 access 的时候修改即可，修改询问复杂度都是一个 $\log$的啦

然而跑得比树剖慢 （怎么办我又想卡树剖了）

然而跑得比 litble 的 lct 快

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp &dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m;

struct N
{
    int f, s[2], sz; LL v, d, t; bool rev;
    int &operator [] (const int a) { return s[a]; }
} e[NS];

int pos(int a) { return e[e[a].f][1] == a; }

bool isrt(int a) { return e[e[a].f][0] != a && e[e[a].f][1] != a; }

void pup(int a)
{
    e[a].sz = e[e[a][0]].sz + e[e[a][1]].sz + 1;
    e[a].d = e[e[a][0]].d + e[e[a][1]].d + e[a].v;
}

void pdown(int a)
{
    int &l = e[a][0], &r = e[a][1]; LL &t = e[a].t;
    if (t)
    {
        if (l) e[l].v += t, e[l].d += 1ll * e[l].sz * t, e[l].t += t;
        if (r) e[r].v += t, e[r].d += 1ll * e[r].sz * t, e[r].t += t;
        t = 0;
    }
    if (e[a].rev)
    {
        if (l) e[l].rev ^= 1, swap(e[l][0], e[l][1]);
        if (r) e[r].rev ^= 1, swap(e[r][0], e[r][1]);
        e[a].rev = 0;
    }
}

void rot(int a)
{
    int f = e[a].f, g = e[f].f, p = pos(a);
    if (!isrt(f)) e[g][pos(f)] = a;
    e[a].f = g, e[f][p] = e[a][!p], e[a][!p] = f, e[f].f = a;
    if (e[f][p]) e[e[f][p]].f = f;
    pup(f), pup(a);
}

int st[NS];

void splay(int a)
{
    st[++st[0]] = a;
    for (int i = a; !isrt(i); i = e[i].f) st[++st[0]] = e[i].f;
    while (st[0]) pdown(st[st[0]--]);
    while (!isrt(a))
    {
        if (!isrt(e[a].f))
        {
            if (pos(a) ^ pos(e[a].f)) rot(a);
            else rot(e[a].f);
        }
        rot(a);
    }
}

void acc(int a)
{
    int b = 0;
    while (a)
    {
        splay(a);
        e[a].v += e[e[a][1]].d - e[b].d;
        e[a][1] = b, pup(a), b = a, a = e[a].f;
    }
}

void evert(int a)
{
    acc(a), splay(a), e[a].rev ^= 1, swap(e[a][0], e[a][1]);
}

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 1; i <= n; i += 1) e[i].sz = 1;
    for (int i = 1, a, b; i < n; i += 1) IN(a), IN(b), e[b + 1].f = a + 1;
    IN(m);
    char opt[3];
    int u, v, d;
    while (m--)
    {
        scanf("%s", opt), IN(u), u++;
        if (opt[0] == 'A')
        {
            IN(v), IN(d), v++, evert(u), acc(v), splay(v);
            e[v].v += d, e[v].d += 1ll * e[v].sz * d, e[v].t += d;
        }
        else evert(1), acc(u), printf("%lld\n", e[u].v);
    }
    return 0;
}