省流题面

定义子块和：在树中选取一些能够组成连通分量的点（也就是只加入和这些点邻接的边，则可以直接让他们全部联通），取这些点的点权加和。本题查询的所有子块都是非空的，这意味着点权为负也有可能。

给定一棵有根树，点有点权，完成以下操作：

1. 查询只包含 $u$ 为根的子树的节点的任意非空最大子块和；
2. 调整点权，之后求包含根的最大子块和
3. 换根，之后求包含新根的最大子块和
4. 切连边，求包含根的最大子块和

15 分做法

设 $f_u$ 为以 $u$ 为根节点且选择 $u$ 的最大子树和，$g_u$ 为 $u$ 为根的子树的最大子树和（均非空）。

不难得到有

$$f_{u}=a_u+\sum\max(f_v,0)\\ g_{u}=\max(f_{u},g_{v}) $$

每次操作后暴力树形 DP 即可

const int N = 3010;
const i64 INF = 1145141919810114514ll;
std::unordered_set<int> e[N];
inline void add_edge(int u, int v) { e[u].insert(v), e[v].insert(u); }
inline void del_edge(int u, int v) { e[u].erase(v), e[v].erase(u); }
int rt;
i64 a[N], f[N], g[N];
void dfs(int u, int fa = 0)
{
    f[u] = a[u], g[u] = -INF;
    for (auto& v : e[u])
        if (v ^ fa)
            dfs(v, u), f[u] += std::max(f[v], 0ll), g[u] = std::max(g[u], g[v]);
    g[u] = std::max(f[u], g[u]);
}

int main()
{
    int n = rd(), q = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd();
    for (int i = 1; i < n; ++i) add_edge(rd(), rd());
    rt = 1, dfs(rt);
    wr(f[rt]), putchar('\n');
    int op = 0, u = 0, x = 0, A = 0, B = 0, C = 0, D = 0;
    while (q--)
    {
        op = rd();
        switch (op)
        {
        case 1: 
            u = rd(), wr(g[u]), putchar('\n'); 
            break;
        case 2: 
            u = rd(), x = rd(), a[u] = x, dfs(rt);  
            wr(f[rt]), putchar('\n'); 
            break;
        case 3:
            rt = rd(), dfs(rt);
            wr(f[rt]), putchar('\n');
            break;
        default:
            A = rd(), B = rd(), C = rd(), D = rd();
            del_edge(A, B), add_edge(C, D), dfs(rt);
            wr(f[rt]), putchar('\n');
            break;
        }
    }
}

30 分做法

注意到树的半径不超过 100，则每个点可以维护一个 multiset，作为备选的 $f_v$，每次从集合中取最大值去计算 $f_u$。

修改的时候则一路暴力向父亲节点跳就行了，复杂度 $O(nh\log n)$。

const int N = 100010;
const i64 INF = 1145141919810114514ll;
struct alt_ans
{
    std::multiset<i64> s;
    void add(i64 v) { s.insert(v); }
    // don't use s.erase(v), it will delete all v. assume v exist
    void del(i64 v) { if (v ^ -INF) s.erase(s.lower_bound(v)); }
    i64 mx_val() const { return s.size() ? *(s.rbegin()) : -INF; }
};
std::vector<int> e[N];
inline void add_edge(int u, int v) { e[u].push_back(v), e[v].push_back(u); }
int fa[N];
i64 a[N], sum_f[N], dp_f[N], dp_g[N];
alt_ans alt_g[N];
void dfs(int u, int f = 0)
{
    fa[u] = f;
    sum_f[u] = 0, dp_g[u] = -INF, dp_f[u] = a[u];
    for (auto& v : e[u]) 
        if (v ^ f) 
            dfs(v, u), sum_f[u] += std::max(dp_f[v], 0ll), alt_g[u].add(dp_g[v]);
    dp_f[u] = a[u] + sum_f[u], dp_g[u] = std::max(alt_g[u].mx_val(), dp_f[u]);
}
void modify(int u, i64 x)
{
    a[u] = x;
    while (u)
    {
        if (fa[u])
        {
            sum_f[fa[u]] -= std::max(dp_f[u], 0ll);
            alt_g[fa[u]].del(dp_g[u]);
        }
        dp_f[u] = a[u] + sum_f[u], dp_g[u] = std::max(alt_g[u].mx_val(), dp_f[u]);
        if (fa[u])
        {
            sum_f[fa[u]] += std::max(dp_f[u], 0ll);
            alt_g[fa[u]].add(dp_g[u]);
        }
        u = fa[u];
    }
}
int main()
{
    int n = rd(), q = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd();
    for (int i = 1; i < n; ++i) add_edge(rd(), rd());
    dfs(1);
    wr(dp_f[1]), putchar('\n');

    int op = 0, u = 0, x = 0, A = 0, B = 0, C = 0, D = 0;
    while (q--)
    {
        op = rd(), assert(op <= 2);
        if (op == 1) u = rd(), wr(dp_g[u]), putchar('\n');
        else u = rd(), x = rd(), modify(u, x), wr(dp_f[1]), putchar('\n');
    }
}

70 分做法

上面的这个状态转移方程好像并不是很好上树，因为还需要利用轻重链剖分来处理。

我们索性换一种方程，设 $f_u$ 是以 $u$ 为根节点且选择 $u$ 的最大子树和，$g_u$ 为 $\max\limits_{v\in \text{subtree(u)},v\ne u} f_v$，也就是去掉 $u$。

此时有：

$$f_u=a_u+\sum\limits_{v\in \text{child}(u)}\max(f_v,0)\\ g_u=\max\limits_{v\in \text{child}(u)}\max(f_v,g_v) $$

然后把 $u$ 的重儿子 $s_u$ 拿出来单独处理。我们设 $f'_u$ 是只考虑 $u$ 和他的轻儿子的子树，选择 $u$ 的最大子树和，同理 $g'_u$ 是上述 $\max$ 去掉重儿子的结果。

• $f'_u=a_u+\sum\limits_{v\ne s_u}\max(f_v,0),g'_u=\max\limits_{v\ne s_u}\max(f_v,g_v)$
• $f_u=f'_u+\max(f_{s_u},0),g_u=\max(g'_u,f_{s_u},g_{s_u})$

于是转移方程可以写为 :

$$\left[\begin{matrix}f'_u&-\infty & f'_u \\0 & 0 & g'_u\\ -\infty&-\infty&0\end{matrix}\right]\times \left[\begin{matrix}f_{s_u}\\g_{s_u}\\0\end{matrix}\right]=\left[\begin{matrix}f_{u}\\g_{u}\\0\end{matrix}\right] $$

然后注意到这个 $g'_u$ 的维护是需要取最大值的，所以还是需要对应地维护一个 multiset。

当然，上述转移方程还可以进行半群优化。不难发现这个矩阵当中只有 $a_{00},a_{02},a_{10},a_{12}$ 四个元素是本质会变化的，具体的半群优化方法见这里。

在查询子树的时候，直接找到他对应的重链并做到链底部区间查询即可。以下给的代码是半群优化过的结果。

const int N = 100010;
const i64 INF = 1145141919810114514ll;
struct alt_ans
{
    std::multiset<i64> s;
    void add(i64 v) { s.insert(v); }
    // don't use s.erase(v), it will delete all v. assume v exist
    void del(i64 v) { if (v ^ -INF) s.erase(s.lower_bound(v)); }
    i64 mx_val() const { return s.size() ? *(s.rbegin()) : -INF; }
};
struct info
{
    i64 a, b, c, d;
    info() { a = 0, b = c = d = -INF; }
    info(i64 f, i64 g) { a = b = f, c = 0, d = g; }
    info operator*(const info &o)
    {
        info ret;
        ret.a = a + o.a, ret.b = std::max(a + o.b, b);
        ret.c = std::max(c + o.a, o.c), ret.d = std::max({c + o.b, o.d, d});
        return ret;
    }
    i64 max_f() const { return std::max(b, 0ll); }
    i64 max_dp() const { return std::max(b, d); }
    i64 max_freal() const { return b; }
};
i64 a[N];
i64 dp_f[N], dp_f2[N], dp_g[N], dp_g2[N];
alt_ans alt_g[N];
info in[N];
void info_sub(int u, const info &x) { dp_f2[u] -= x.max_f(), alt_g[u].del(x.max_dp()); }
void info_add(int u, const info &x) { dp_f2[u] += x.max_f(), alt_g[u].add(x.max_dp()); }
void info_adjust(int u) { dp_g2[u] = alt_g[u].mx_val(), in[u] = info(dp_f2[u], dp_g2[u]); }
namespace seg
{
    int *rev_dfn;
    struct node
    {
        int lc, rc;
        info sum;
    } tr[N << 1];
    int rt[N], L[N], R[N], cnt;
    void pushup(int u) { tr[u].sum = tr[tr[u].lc].sum * tr[tr[u].rc].sum; }
    int _build(int l, int r)
    {
        int u = ++cnt;
        if (l == r)
            return tr[u].sum = in[rev_dfn[l]], u;
        int m = (l + r) >> 1;
        tr[u].lc = _build(l, m), tr[u].rc = _build(m + 1, r);
        return pushup(u), u;
    }
    void build(int i, int l, int r) { L[i] = l, R[i] = r, rt[i] = _build(L[i], R[i]); }
    void _upd(int u, int l, int r, int pos)
    {
        if (l == r)
            tr[u].sum = in[rev_dfn[l]]; // modify g outside first.
        else
        {
            int m = (l + r) >> 1;
            if (pos <= m)
                _upd(tr[u].lc, l, m, pos);
            else
                _upd(tr[u].rc, m + 1, r, pos);
            pushup(u);
        }
    }
    void upd(int i, int pos) { _upd(rt[i], L[i], R[i], pos); }
    info _query(int u, int l, int r, int L, int R)
    {
        if (r < L || l > R || l > r)
            return info();
        if (l <= L && R <= r)
            return tr[u].sum;
        int M = (L + R) >> 1;
        return _query(tr[u].lc, l, r, L, M) * _query(tr[u].rc, l, r, M + 1, R);
    }
    info query(int i, int l, int r) { return _query(rt[i], l, r, L[i], R[i]); }
    info query_rt(int i) { return tr[rt[i]].sum; }
}
namespace HLD
{
    int n, rt;
    int to[N << 1], nxt[N << 1], h[N], ecnt;
    void add_edge(int u, int v) { to[++ecnt] = v, nxt[ecnt] = h[u], h[u] = ecnt; }
    void link(int u, int v) { add_edge(u, v), add_edge(v, u); }

    int f[N], sz[N], dep[N], son[N];
    int dfn[N], rev_dfn[N], top[N], bot[N], dfst;

    void dfs1(int u, int fa)
    {
        f[u] = fa, sz[u] = 1, dep[u] = dep[fa] + 1;
        dp_f[u] = a[u], dp_g[u] = -INF; // extra dp
        for (int i = h[u], v = to[i]; i; i = nxt[i], v = to[i])
        {
            if (v == fa)
                continue;
            dfs1(v, u), sz[u] += sz[v];
            if (sz[son[u]] < sz[v])
                son[u] = v;
            dp_f[u] += std::max(dp_f[v], 0ll);
            dp_g[u] = std::max({dp_g[u], dp_f[v], dp_g[v]});
        }
    }
    void dfs2(int u, int topf)
    {
        top[u] = topf, dfn[u] = ++dfst, rev_dfn[dfst] = u;
        if (son[u])
            dfs2(son[u], topf), bot[u] = bot[son[u]];
        else
            bot[u] = u;
        dp_f2[u] = a[u];
        for (int i = h[u], v = to[i]; i; i = nxt[i], v = to[i])
        {
            if (v == f[u] || v == son[u])
                continue;
            dfs2(v, v);
            dp_f2[u] += std::max(dp_f[v], 0ll);
            alt_g[u].add(std::max(dp_f[v], dp_g[v]));
        }
        dp_g2[u] = alt_g[u].mx_val();
        in[u] = info(dp_f2[u], dp_g2[u]);
    }
    void build(int _rt, int _n)
    {
        n = _n, rt = _rt;
        dfs1(rt, 0), dfs2(rt, rt), seg::rev_dfn = rev_dfn;
        for (int i = 1; i <= n; ++i)
            if (top[i] == i)
                seg::build(i, dfn[i], dfn[bot[i]]);
    }
    void upd(int u, i64 v)
    {
        dp_f2[u] += (v - a[u]), info_adjust(u), a[u] = v;
        while (u)
        {
            info a = seg::query_rt(top[u]);
            seg::upd(top[u], dfn[u]);
            info b = seg::query_rt(top[u]);
            u = f[top[u]];
            if (u) info_add(u, b), info_sub(u, a), info_adjust(u);
        }
    }
    info query(int u) { return seg::query(top[u], dfn[u], dfn[bot[u]]); }
}
int main()
{
    int n = rd(), q = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd();
    for (int i = 1; i < n; ++i) HLD::link(rd(), rd());
    HLD::build(1, n);
    wr(HLD::query(1).max_freal()), putchar('\n');
    int op = 0, u = 0, x = 0, A = 0, B = 0, C = 0, D = 0;
    while (q--)
    {
        op = rd(), assert(op <= 2);
        if (op == 1) u = rd(), wr(HLD::query(u).max_dp()), putchar('\n');
        else u = rd(), x = rd(), HLD::upd(u, x), wr(HLD::query(1).max_freal()), putchar('\n');
    }
}

100 分做法

100 分需要对 LCT 拥有较为深刻的认知才能做出来。首先在虚实链剖分的层面，单独把虚子树拎出来维护的思想和轻重链剖分是类似的。接下来主要是处理以下几个问题：

• 在 access 的时候，每个节点里的备选答案 $f_u$ 集合是会变化的，需要使用 multiset 持续维护
• 在查询某个子树的情况下，需要先对当前的根进行 makeroot，并在该根下对查询子树的父亲进行 access 操作（寻找有根树意义下的父亲也是 LCT 的基础操作之一，access 则可做到信息上的切断）
• LCT 在维护换根、切连边操作的时候会存在节点的翻转操作。由于半群运算是无交换律的，因此我们需要维护一个反向半群运算的计算过程，在翻转时两者交换
• 在切连边的时候也需要将 LCT 内儿子的信息从父亲的信息切掉/增加上去

更为具体和完整的操作见代码。

const int N = 100010;
const i64 INF = 1145141919810114514ll;
struct alt_ans
{
    std::multiset<i64> s;
    void add(i64 v) { s.insert(v); }
    // don't use s.erase(v), it will delete all v. assume v exist
    void del(i64 v) { if (v ^ -INF) s.erase(s.lower_bound(v)); }
    i64 mx_val() const { return s.size() ? *(s.rbegin()) : -INF; }
};
struct info
{
    i64 a, b, c, d;
    info() { a = 0, b = c = d = -INF; }
    info(i64 f, i64 g) { a = b = f, c = 0, d = g; }
    info& operator=(const info& o) { return a = o.a, b = o.b, c = o.c, d = o.d, *this; }
    info operator*(const info &o)
    {
        info ret;
        ret.a = a + o.a, ret.b = std::max(a + o.b, b);
        ret.c = std::max(c + o.a, o.c), ret.d = std::max({c + o.b, o.d, d});
        ret.a = std::max(ret.a, -INF), ret.b = std::max(ret.b, -INF), ret.c = std::max(ret.c, -INF), ret.d = std::max(ret.d, -INF);
        return ret;
    }
    i64 max_f() const { return std::max(b, 0ll); };
    i64 max_freal() const { return b; }
    i64 max_dp() const { return std::max(b, d); }
};
namespace LCT
{
    int rt;
    struct node
    {
        int fa, ch[2];
        bool rev;
        i64 dp_f;
        alt_ans alt_g;
        info val, sum, rsum;
    } no[N];
    void pushup(int u)
    {
        no[u].val = info(no[u].dp_f, no[u].alt_g.mx_val());
        no[u].sum = no[no[u].ch[0]].sum * no[u].val * no[no[u].ch[1]].sum;
        no[u].rsum = no[no[u].ch[1]].rsum * no[u].val * no[no[u].ch[0]].rsum;
    }
    void add(int u, int v) { no[u].dp_f += no[v].sum.max_f(), no[u].alt_g.add(no[v].sum.max_dp()); }
    void sub(int u, int v) { no[u].dp_f -= no[v].sum.max_f(), no[u].alt_g.del(no[v].sum.max_dp()); }
    bool nroot(int x) { return no[no[x].fa].ch[0] == x || no[no[x].fa].ch[1] == x; }
    bool son(int x) { return no[no[x].fa].ch[1] == x; }
    void rotate(int x)
    {
        bool f = son(x);
        int y = no[x].fa, z = no[y].fa, w = no[x].ch[f ^ 1];
        if (nroot(y))
            no[z].ch[son(y)] = x;
        no[x].fa = z, no[x].ch[f ^ 1] = y, no[y].fa = x, no[y].ch[f] = w;
        if (w)
            no[w].fa = y;
        pushup(y), pushup(x);
    }
    void reverse(int x)
    {
        std::swap(no[x].ch[0], no[x].ch[1]);
        std::swap(no[x].sum, no[x].rsum), no[x].rev ^= 1;
    }
    void pushdown(int x)
    {
        if (no[x].rev)
        {
            if (no[x].ch[0])
                reverse(no[x].ch[0]);
            if (no[x].ch[1])
                reverse(no[x].ch[1]);
            no[x].rev = 0;
        }
    }
    void pushdownall(int x)
    {
        if (nroot(x))
            pushdownall(no[x].fa);
        pushdown(x);
    }
    void Splay(int x)
    {
        pushdownall(x);
        while (nroot(x))
        {
            if (nroot(no[x].fa))
                rotate(son(x) == son(no[x].fa) ? no[x].fa : x);
            rotate(x);
        }
    }
    int access(int x)
    {
        int y;
        for (y = 0; x; y = x, x = no[x].fa)
        {
            Splay(x);
            // x's right child become x's virtual son, add it to val
            if (no[x].ch[1])
                add(x, no[x].ch[1]);
            // y become x's real son, minus its val
            if (y)
                sub(x, y);
            no[x].ch[1] = y;
            pushup(x);
        }
        return y;
    }
    int findroot(int x)
    {
        access(x), Splay(x);
        while (no[x].ch[0])
            pushdown(x), x = no[x].ch[0];
        return Splay(x), x;
    }
    bool connected(int x, int y) { return findroot(x) == findroot(y); }
    void changert(int _rt) { rt = _rt; }
    void makeroot(int x) { access(x), Splay(x), reverse(x); }
    int lca(int x, int y) { return makeroot(rt), access(x), access(y); }
    int findfa(int x)
    {
        makeroot(rt), access(x), Splay(x);
        x = no[x].ch[0];
        if (!x)
            return x;
        while (no[x].ch[1])
            pushdown(x), x = no[x].ch[1];
        return Splay(x), x;
    }
    void split(int x, int y) { makeroot(x), access(y), Splay(y); }
    void link(int x, int y)
    {
        makeroot(x), makeroot(y);
        if (findroot(y) ^ x)
            no[x].fa = y, add(y, x);
        pushup(y);
    }
    void cut(int x, int y)
    {
        split(x, y);
        if (no[y].ch[0] == x && !no[x].ch[1])
            no[y].ch[0] = no[x].fa = 0, pushup(y);
    }
    void init(int x, i64 val) { makeroot(x), no[x].dp_f = val, pushup(x); }
    void add_single(int x, i64 delta) { makeroot(x), no[x].dp_f += delta, pushup(x); }
    i64 query(int x, bool flag)
    {
        makeroot(rt);
        if (x ^ rt) access(findfa(x));
        return Splay(x), flag ? no[x].sum.max_dp() : no[x].sum.max_freal();
    }
}
i64 a[N];
int main()
{
    int n = rd(), q = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd(), LCT::init(i, a[i]);
    for (int i = 1; i < n; ++i) LCT::link(rd(), rd());
    LCT::changert(1);
    wr(LCT::query(1, 0)), putchar('\n');
    int op = 0, u = 0, x = 0, A = 0, B = 0, C = 0, D = 0;
    while (q--)
    {
        op = rd();
        switch (op)
        {
        case 1: 
            u = rd(), wr(LCT::query(u, 1)), putchar('\n'); 
            break;
        case 2: 
            u = rd(), x = rd(), LCT::add_single(u, x - a[u]), a[u] = x;  
            wr(LCT::query(LCT::rt, 0)), putchar('\n'); 
            break;
        case 3:
            u = rd(), LCT::changert(u);
            wr(LCT::query(LCT::rt, 0)), putchar('\n');
            break;
        default:
            A = rd(), B = rd(), C = rd(), D = rd();
            LCT::cut(A, B), LCT::link(C, D);
            wr(LCT::query(LCT::rt, 0)), putchar('\n');
            break;
        }
    }
}