题解 P3642 [APIO2016]烟火表演

· · 题解

首先 DP 设 f(u,i) 表示 u 为根的子树内所有叶子到 u 的爆炸时间为 i 的最小代价。

代价函数是一个绝对值函数，可以发现 f(u,x) 的图像是一个下凸包。

将 u 的所有儿子合并就是凸包相加。

加入 u 到 \mathrm{fa}(u) 的边 c_u 的代价时，

f'(u,i)=\min_{0\le j\le i}\{|c_u-j|+f(u,i-j)|\}

也就是函数 |c_u-x| 和 f(u,x) 形成的凸包的闵可夫斯基和（注：两个点集 A,B 的闵可夫斯基和为 \{x+y\mid x\in A,y\in B\}）。

模拟一下闵可夫斯基和的归并过程，在这里只需要将 f(u,x) 中斜率为 0 的线段向后平移，前面插入向量 (c_u,-c_u)，后面只保留一条斜率为 1 的射线。

具体实现，用拐点表示法可以方便地将两个凸包相加，用可并堆维护凸包的所有拐点，每个拐点同时代表后面线段斜率 +1。

每次合并子树注意结尾只保留一个斜率为 +1 的射线。

最后取斜率 0 处的值，可以用凸包开头的点值 \sum_i c_i 减去每个拐点的横坐标。

代码：

#include <bits/stdc++.h>

// 这是个自适应的左偏树，不用记 dist
struct Node {
    int64_t pos;
    Node *ls, *rs;

    Node(int64_t v) : pos(v), ls{}, rs{} {}
};

Node *merge(Node *x, Node *y) {
    if (!x) return y;
    if (!y) return x;
    if (x->pos < y->pos) std::swap(x, y);
    x->rs = merge(x->rs, y);
    std::swap(x->ls, x->rs);
    return x;
}

void pop(Node *&x) {
    x = merge(x->ls, x->rs);
}

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

    int n, m;
    std::cin >> n >> m;
    std::vector<int> fa(n + m), c(n + m), son(n + m);
    for (int i = 1; i < n + m; ++i) {
        std::cin >> fa[i] >> c[i];
        --fa[i];
        ++son[fa[i]];
    }

    std::vector<Node *> f(n + m);
    for (int u = n + m - 1; u > 0; --u) {
        int64_t l = 0;
        int64_t r = 0;
        if (u < n) {
            --son[u];
            while (son[u]--) pop(f[u]);
            r = f[u]->pos;
            pop(f[u]);
            l = f[u]->pos;
            pop(f[u]);
        }
        // [l, r] 就是斜率为 0 的线段
        f[u] = merge(f[u], merge(new Node(l + c[u]), new Node(r + c[u])));
        f[fa[u]] = merge(f[fa[u]], f[u]);
    }

    while (son[0]--) pop(f[0]);
    int64_t ans = std::accumulate(c.begin(), c.end(), 0ll);
    while (f[0]) {
        ans -= f[0]->pos;
        pop(f[0]);
    }
    std::cout << ans << '\n';

    return 0;
}