Codeforces 树上启发式合并与李超线段树合并：CF600E 与 CF932F 题解

子树信息汇聚的两类常见结构

在以 $1$ 为根的有根树上，若节点 $u$ 的答案或 DP 状态依赖于子树 $\operatorname{subtree}(u)$ 内所有节点的信息，直接对每个节点遍历子树需要 $O(n^2)$ 时间。根据信息是否支持高效可逆修改与凸包查询，常用以下两种做法：

场景特征	适用结构	时间复杂度	空间复杂度
离线子树频率/众数统计，单点增删 $O(1)$ ，无修改操作	DSU on Tree（树上启发式合并）	$O(n \log n)$	$O(n)$
树上 DP 转移形如 $\min_{v \in \operatorname{subtree}(u)} (k_v x_u + b_v)$	动态开点李超线段树合并	$O(n \log X)$	$O(n \log X)$

本文通过 CF600E 与 CF932F 详细分析这两种方法。

CF600E Lomsat gelral：DSU on Tree

题意与重儿子分解

给定一棵 $n$ （ $n \le 10^5$ ）个节点的有根树，根节点为 $1$ ，每个节点 $u$ 有颜色 $c_u \in [1, n]$ 。若颜色 $c$ 在 $u$ 的子树中出现次数最多（可并列），称颜色 $c$ 支配子树 $u$ 。求每个节点 $u$ 的所有支配颜色编号之和。

设 $\operatorname{sz}[u]$ 为子树 $u$ 的大小，定义 $u$ 的重儿子 $\operatorname{son}[u]$ 为子树大小最大的子节点：

\operatorname{son}[u] = \arg\max_{v \in \operatorname{child}(u)} \operatorname{sz}[v]

其余子节点称为轻儿子。由重链剖分的经典性质，任意节点 $x$ 到根节点的路径上，经过的轻边数量不超过 $\lfloor \log_2 n \rfloor$ 。

递归复用重儿子桶

维护一个全局颜色计数数组 cnt[c]、当前最大出现次数 max_cnt 以及对应的颜色编号和 sum_color。计算 $\operatorname{dfs}(u, \text{keep})$ 的流程如下：

对 $u$ 的所有轻儿子 $v$ ，递归调用 $\operatorname{dfs}(v, \text{false})$ ，并在返回时清空 $v$ 子树对全局桶的贡献；
若 $u$ 存在重儿子 $w = \operatorname{son}[u]$ ，递归调用 $\operatorname{dfs}(w, \text{true})$ ，保留 $w$ 子树在全局桶中的信息；
将 $u$ 本身及所有轻儿子子树中的节点暴力加入全局桶，此时桶中恰好包含 $\operatorname{subtree}(u)$ 的完整分布，记录 $\operatorname{ans}[u] = \text{sum\_color}$ ；
若 $\text{keep} = \text{false}$ ，遍历 $\operatorname{subtree}(u)$ 将其从桶中清空，并将 max_cnt 与 sum_color 置零。

复杂度证明

一个节点 $x$ 被暴力加入或清除，当且仅当当前正在处理它的某个祖先 $u$ ，且 $x$ 位于 $u$ 的某个轻儿子子树中（即 $x \to u$ 路径的第一步是轻边）。因为每个节点到根路径上至多有 $O(\log n)$ 条轻边，每个节点被暴力访问的次数不超过 $2 \log_2 n$ 次，总时间复杂度严格为 $O(n \log n)$ ，空间复杂度 $O(n)$ 。

C++ 实现

利用 DFS 序区间 $[L_u, R_u]$ 可将子树遍历转化为连续数组循环，显著减小常数。

#include <iostream>
#include <vector>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    if (!(std::cin >> n)) return 0;

    std::vector<int> color(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> color[i];
    }

    std::vector<std::vector<int>> adj(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    std::vector<int> sz(n + 1), son(n + 1, 0), tin(n + 1), tout(n + 1), node_at(n + 1);
    int timer = 0;

    auto prep = [&](auto& self, int u, int p) -> void {
        sz[u] = 1;
        tin[u] = ++timer;
        node_at[timer] = u;
        for (int v : adj[u]) {
            if (v == p) continue;
            self(self, v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[son[u]]) {
                son[u] = v;
            }
        }
        tout[u] = timer;
    };
    prep(prep, 1, 0);

    std::vector<int> cnt(n + 1, 0);
    int max_cnt = 0;
    i64 sum_color = 0;
    std::vector<i64> ans(n + 1, 0);

    auto add_node = [&](int u) {
        int c = color[u];
        ++cnt[c];
        if (cnt[c] > max_cnt) {
            max_cnt = cnt[c];
            sum_color = c;
        } else if (cnt[c] == max_cnt) {
            sum_color += c;
        }
    };

    auto dfs = [&](auto& self, int u, int p, bool keep) -> void {
        for (int v : adj[u]) {
            if (v == p || v == son[u]) continue;
            self(self, v, u, false);
        }
        if (son[u]) {
            self(self, son[u], u, true);
        }
        add_node(u);
        for (int v : adj[u]) {
            if (v == p || v == son[u]) continue;
            for (int t = tin[v]; t <= tout[v]; ++t) {
                add_node(node_at[t]);
            }
        }
        ans[u] = sum_color;
        if (!keep) {
            for (int t = tin[u]; t <= tout[u]; ++t) {
                cnt[color[node_at[t]]] = 0;
            }
            max_cnt = 0;
            sum_color = 0;
        }
    };
    dfs(dfs, 1, 0, true);

    for (int i = 1; i <= n; ++i) {
        std::cout << ans[i] << (i == n ? '\n' : ' ');
    }
    return 0;
}

CF932F Escape Through Leaf：李超线段树合并

题意与转移方程

给定一棵 $n$ （ $n \le 10^5$ ）个节点的有根树，每个节点有两个权值 $a_u, b_u \in [-10^5, 10^5]$ 。从节点 $u$ 可以直接跳到其子树内的任意节点 $v$ （ $v \in \operatorname{subtree}(u), v \ne u$ ），单步代价为 $a_u \cdot b_v$ 。求从每个节点 $u$ 跳到某个叶子节点的最小总代价 $dp[u]$ 。

对于叶子节点， $dp[u] = 0$ ；对于非叶节点：

dp[u] = \min_{v \in \operatorname{subtree}(u) \setminus \{u\}} \left( b_v \cdot a_u + dp[v] \right)

每个子树节点 $v$ 提供一条一次函数 $L_v(x) = b_v x + dp[v]$ ，而 $dp[u]$ 就是在点 $x = a_u$ 处查询子树内所有直线纵坐标的最小值。

动态开点李超线段树与合并复杂度

由于横坐标定义域为 $[-M, M]$ （ $M = 10^5$ ）且自变量 $a_u$ 与斜率 $b_v$ 均无单调性，我们使用动态开点李超线段树在值域 $[-M, M]$ 上维护直线下包络：

每个线段树节点维护区间 $[l, r]$ 的中点 $\operatorname{mid} = \lfloor (l+r)/2 \rfloor$ 处取值最小的优势直线 line[id]。
插入新直线 $L_{\text{new}}$ 到节点 id 时，比较 $L_{\text{new}}(\operatorname{mid})$ 与 line[id] 在 $\operatorname{mid}$ 处的函数值，令较小者成为新的 line[id]，较大者（记为 $L_{\text{loser}}$ ）至多在左半区间或右半区间之一优于 line[id]，仅向该侧递归下传。

合并两棵对应同一区间 $[l, r]$ 的李超线段树节点 merge(p, q, l, r)：

若 p 或 q 为空，直接返回非空者；
递归合并左右子树：lc[p] = merge(lc[p], lc[q], l, mid)，rc[p] = merge(rc[p], rc[q], mid+1, r)；
将节点 q 上保存的优势直线 line[q] 插入以 p 为根的区间 $[l, r]$ 中。

时间复杂度势能分析：定义一条直线 $L$ 在李超树中所处节点的深度为 $d(L) \in [0, \lceil \log_2(2M) \rceil]$ 。每次 merge(p, q) 在非空重合节点处调用 insert(p, l, r, line[q]) 时，被下传的直线每递归一层，其在树中的深度 $d(L)$ 严格加 $1$ 。因为共有 $n$ 条直线，每条直线的深度最多从 $0$ 增加到 $\lceil \log_2(2M) \rceil$ ，所有合并操作的总耗时严格上界为 $O(n \log M)$ 。

C++ 实现

#include <algorithm>
#include <iostream>
#include <vector>

using i64 = long long;

constexpr i64 INF = 1LL << 60;
constexpr int X_MIN = -100000;
constexpr int X_MAX = 100000;

struct Line {
    i64 k = 0;
    i64 b = INF;
    i64 eval(i64 x) const { return k * x + b; }
};

struct Node {
    Line ln;
    int lc = 0;
    int rc = 0;
};

class LiChaoTree {
public:
    explicit LiChaoTree(int max_nodes) {
        tr.reserve(max_nodes);
        tr.push_back(Node{}); // 0 号为空节点
    }

    void insert(int& u, int l, int r, Line nw) {
        if (!u) {
            u = new_node(nw);
            return;
        }
        int mid = l + (r - l) / 2;
        if (nw.eval(mid) < tr[u].ln.eval(mid)) {
            std::swap(nw, tr[u].ln);
        }
        if (l == r) return;
        if (nw.eval(l) < tr[u].ln.eval(l)) {
            insert(tr[u].lc, l, mid, nw);
        } else if (nw.eval(r) < tr[u].ln.eval(r)) {
            insert(tr[u].rc, mid + 1, r, nw);
        }
    }

    i64 query(int u, int l, int r, int x) const {
        if (!u) return INF;
        i64 res = tr[u].ln.eval(x);
        if (l == r) return res;
        int mid = l + (r - l) / 2;
        if (x <= mid) {
            return std::min(res, query(tr[u].lc, l, mid, x));
        }
        return std::min(res, query(tr[u].rc, mid + 1, r, x));
    }

    int merge(int p, int q, int l, int r) {
        if (!p || !q) return p | q;
        int mid = l + (r - l) / 2;
        tr[p].lc = merge(tr[p].lc, tr[q].lc, l, mid);
        tr[p].rc = merge(tr[p].rc, tr[q].rc, mid + 1, r);
        insert(p, l, r, tr[q].ln);
        return p;
    }

private:
    std::vector<Node> tr;

    int new_node(Line ln) {
        tr.push_back(Node{ln, 0, 0});
        return static_cast<int>(tr.size()) - 1;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    if (!(std::cin >> n)) return 0;

    std::vector<i64> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i) std::cin >> a[i];
    for (int i = 1; i <= n; ++i) std::cin >> b[i];

    std::vector<std::vector<int>> adj(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    LiChaoTree lct(n * 20);
    std::vector<int> root(n + 1, 0);
    std::vector<i64> dp(n + 1, 0);

    auto dfs = [&](auto& self, int u, int p) -> void {
        bool is_leaf = true;
        for (int v : adj[u]) {
            if (v == p) continue;
            is_leaf = false;
            self(self, v, u);
            root[u] = lct.merge(root[u], root[v], X_MIN, X_MAX);
        }
        dp[u] = is_leaf ? 0 : lct.query(root[u], X_MIN, X_MAX, static_cast<int>(a[u]));
        lct.insert(root[u], X_MIN, X_MAX, Line{b[u], dp[u]});
    };
    dfs(dfs, 1, 0);

    for (int i = 1; i <= n; ++i) {
        std::cout << dp[i] << (i == n ? '\n' : ' ');
    }
    return 0;
}