【题解】【模板】动态 dp 全局平衡二叉树 LUOGU – 4719

题目传送门=￣ω￣=

这题主要是看到了 LUOGU 题解里排名第一的那个全局平衡二叉树的博客浪费了我很多时间，讲又没有讲清楚

讲真，那位博主不知道在写些什么鬼，压行压得亲妈都不认识了，一行一百多个字，右大括号后面还写代码，大概就是他写完了以后再强行压行吧，根本没法 gdb

这个就是动态版的 “没有上司的舞会” 嘛

设 $f _ {x, 0}$表示不选择 $x$时 $x$及其子树的最大贡献，$f _ {x, 1}$表示选择 $x$时 $x$及其子树的最大贡献

就有：

$$f _ {x, 0} = \sum _ y \max(f _ {y, 0}, f _ {y, 1})$$
$$f _ {x, 1} = v _ x + \sum _ y f _ {y, 0}$$

其中 $y$是 $x$的一个儿子，$v _ x$是 $x$的权值

假如树链剖分了，$x$的重儿子是 $h$，$z$是 $x$的某个轻儿子

那么有：

$$f _ {x, 0} = \max(f _ {h, 0}, f _ {h, 1}) + \sum _ z \max(f _ {z, 0}, f _ {z, 1})$$
$$f _ {x, 1} = v _ x + f _ {h, 0} + \sum _ z f _ {z, 0}$$

设 $g _ {x, 0} = \sum _ z \max(f _ {z, 0}, f _ {z, 1})$，$g _ {x, 1} = v _ x + \sum _ z f _ {z, 0}$

$$f _ {x, 0} = \max(f _ {h, 0}, f _ {h, 1}) + g _ {x, 0}$$
$$f _ {x, 1} = f _ {h, 0} + g _ {x, 1}$$

发现这个东西就有点像矩阵乘法，从 $\left[ \begin{matrix}f _ {h, 0} & f _ {h, 1}\end{matrix} \right]$经过由 $g$决定的某个矩阵转移到 $\left[ \begin{matrix}f _ {x, 0} & f _ {x, 1}\end{matrix} \right]$

这个叫做广义矩阵乘法（吧）

我们这样构造矩阵乘法：

$$A \times B = C$$
$$C _ {i, j} = \max _ k (A _ {i, k} + B _ {k, j})$$
没错，就是 floyd，并且可以验证它也具有结合律

我们构造一个这样的转移矩阵：

$$
\left[
\begin{matrix}
g _ {x, 0} & g _ {x, 1} \\
g _ {x, 0} & -\infty
\end{matrix}
\right]
$$

可以验证，下式成立：

$$
\left[ \begin{matrix}f _ {h, 0} & f _ {h, 1}\end{matrix} \right] \times
\left[
\begin{matrix}
g _ {x, 0} & g _ {x, 1} \\
g _ {x, 0} & -\infty
\end{matrix}
\right]
= \left[ \begin{matrix}f _ {x, 0} & f _ {x, 1}\end{matrix} \right]
$$

于是 $\left[ \begin{matrix}f _ {x, 0} & f _ {x, 1}\end{matrix} \right]$可以由 $x$下方的重链的转移矩阵连乘得到（提示：每条重链末端一定是个叶子结点）

搞个线段树，维护每个区间内矩阵的连乘结果矩阵

修改的时候每向上跳一条轻边就更新一下父亲的 $g$，线段树动态维护区间嘛

询问就是查根节点所在重链的矩阵连乘结果

这样是 $O(\log _ 2 ^ 2)$的，还带个矩乘的复杂度

用 lct 可以做到 $O(\log _ 2 n)$，然而常数太大

可以建一棵静态的 lct——也就是全局平衡二叉树！

做法大概就是树链剖分以后不用线段树维护，而是每个重链搞个二叉查找树 bst——就像 lct 那样，lct 的每个剖分链都是一个 splay

对重链建立 bst 的时候，每次找到加权重心——每个点的权值为其轻子树大小之和（自身子树大小减去重儿子子树大小），递归建树（当然，bst 的每个点的左儿子在重链上都比它浅，右儿子都比它深，它就是静态的 lct 呀），这样在 bst 上每向上跳一下，子树大小就会翻倍

在重链之间用 lct 一样的虚边相连——儿子连向父亲，父亲不连向儿子

这样在 bst 上条一条虚边，子树大小也会翻倍，总的时限自然就是一个 $\log$了

具体细节看代码吧_(:з」∠)_

（下面这个代码是卡了常的，能过加强版，需要加个强制在线和开大数据范围）

（加强版其实意义不大，整个就是无聊卡长，弄得我还写了人生第一份 fread 读入优化）

代码：

#include <bits/stdc++.h>

#define NS (100005)
#define INF (1000000000)

using namespace std;

inline char getC()
{
    static char buff[100000], *p = buff, *q = buff;
    if (p == q)
    {
        q = (p = buff) + fread(buff, 1, 100000, stdin);
        if (p == q) return EOF;
    }
    return *p++;
}

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

inline int Max(int a, int b) { return a > b ? a : b; }

int n, m, V[NS], hs[NS], sz[NS];

struct graph
{
    int head[NS], nxt[NS << 1], to[NS << 1], sz;
    graph() { memset(head, -1, sizeof(head)), sz = 0; }
    void push(int a, int b)
    {
        nxt[sz] = head[a], to[sz] = b, head[a] = sz++;
    }
    int operator [] (const int a) const { return to[a]; }
} g;

struct M
{
    int d[2][2];
    int (& operator [] (const int a))[2] { return d[a]; }
    inline int mx()
    {
        return Max(Max(d[0][0], d[0][1]), Max(d[1][0], d[1][1]));
    }
    void operator *= (M &oth)
    {
        static int tmp[2][2];
        tmp[0][0] = Max(d[0][0] + oth[0][0], d[0][1] + oth[1][0]);
        tmp[0][1] = Max(d[0][0] + oth[0][1], d[0][1] + oth[1][1]);
        tmp[1][0] = Max(d[1][0] + oth[0][0], d[1][1] + oth[1][0]);
        tmp[1][1] = Max(d[1][0] + oth[0][1], d[1][1] + oth[1][1]);
        memmove(d, tmp, sizeof(d));
    }
};

int root, A[NS];

struct N { int f, s[2]; M d, m; } e[NS];

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

void dfs(int a, int fa)
{
    sz[a] = 1, e[a].d[0][1] = V[a], e[a].d[1][1] = -INF;
    for (int i = g.head[a], mx = 0; ~i; i = g.nxt[i])
        if (g[i] != fa)
        {
            dfs(g[i], a), sz[a] += sz[g[i]];
            if (sz[g[i]] > mx) mx = sz[g[i]], hs[a] = g[i];
        }
}

inline void pup(int a)
{
    e[a].m = e[e[a].s[1]].m;
    e[a].m *= e[a].d;
    if (e[a].s[0]) e[a].m *= e[e[a].s[0]].m;
}

inline void pupd(int a, int b, bool f)
{
    if (f)
    {
        e[a].d[0][0] += e[b].m.mx(), e[a].d[1][0] = e[a].d[0][0];
        e[a].d[0][1] += Max(e[b].m[0][0], e[b].m[1][0]);
    }
    else
    {
        e[a].d[0][0] -= e[b].m.mx(), e[a].d[1][0] = e[a].d[0][0];
        e[a].d[0][1] -= Max(e[b].m[0][0], e[b].m[1][0]);
    }
}

int build(int l, int r)
{
    if (l > r) return 0;
    int sum = 0, tot = sz[A[l]], mid = l;
    for (int i = l; i <= r; i += 1) sum += sz[A[i]];
    while ((tot << 1) <= sum) mid++, tot += sz[A[mid]];
    int a = A[mid];
    e[a].s[0] = build(l, mid - 1), e[a].s[1] = build(mid + 1, r);
    if (e[a].s[0]) e[e[a].s[0]].f = a;
    if (e[a].s[1]) e[e[a].s[1]].f = a;
    pup(a);
    return a;
}

bool book[NS];

int constract(int a)
{
    for (int i = a; i; i = hs[i]) book[i] = 1;
    for (int i = a; i; i = hs[i])
        for (int j = g.head[i]; ~j; j = g.nxt[j])
            if (!book[g[j]])
            {
                int k = constract(g[j]);
                e[k].f = i, pupd(i, k, 1);
            }
    A[0] = 0;
    for (int i = a; i; i = hs[i]) A[++A[0]] = i;
    for (int i = 1; i < A[0]; i += 1) sz[A[i]] -= sz[A[i + 1]];
    return build(1, A[0]);
}

void modify(int a, int k)
{
    e[a].d[0][1] += k - V[a], V[a] = k;
    while (a)
    {
        if (e[a].f && isrt(a))
            pupd(e[a].f, a, 0), pup(a), pupd(e[a].f, a, 1);
        else pup(a);
        a = e[a].f;
    }
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), e[0].m[0][1] = e[0].m[1][0] = -INF, e[0].d = e[0].m;
    for (int i = 1; i <= n; i += 1) IN(V[i]);
    for (int i = 1, a, b; i < n; i += 1)
        IN(a), IN(b), g.push(a, b), g.push(b, a);
    dfs(1, 0), root = constract(1);
    for (int i = 1, x, y; i <= m; i += 1)
    {
        IN(x), IN(y), modify(x, y);
        printf("%d\n", e[root].m.mx());
    }
    return 0;
}