1. 核心算法思想：Slope Trick

DP 状态定义

设 $f_u(x)$ 表示以 $u$ 为根的子树中，所有叶子节点（烟花）到 $u$ 的距离都调整为 $x$ 时，子树内所需的最小代价。

函数性质

$f_u(x)$ 具有很好的数学性质：

1. 凸函数（Convex）：函数的斜率是单调不减的。
2. 分段线性（Piecewise Linear）：函数由多段直线组成。
3. 整数斜率：每一段的斜率都是整数。

由于这些性质，我们不需要存储整个函数，只需要存储函数斜率发生变化的转折点（Kinks/Breakpoints）。我们可以用一个大根堆（Priority Queue）来维护这些转折点。堆中存储的是斜率 $k$ 变为 $k+1$ 的那个横坐标 $x$。

2. 状态转移与操作

对于节点 $u$ 和它的子节点 $v$，以及连接它们的边权 $w$，转移分为两步：

第一步：合并子树 (Merge)

函数相加对应于转折点的集合合并。

• 代码体现：使用 __gnu_pbds 库中的 priority_queue（配对堆 pairing_heap_tag）的 join 操作，将子节点的堆合并到父节点中。

第二步：加上当前边 (Add Edge)

我们需要考虑边权 $w$ 的调整。新的函数 $f_u(x)$ 由 $F_{temp}(x)$ 加上边权调整代价 $|w' - w|$ 得到。 数学推导表明，这个操作等价于对 $F_{temp}(x)$ 的图像进行以下变换：

1. 斜率修正：$F_{temp}(x)$ 的右侧斜率可能非常大（等于子节点数量）。但加上一条边后，对于非常大的 $x$，我们可以通过单纯增加这条边的长度来满足，代价增长率（斜率）最大只能是 1。因此，我们需要将 $F_{temp}(x)$ 大于 1 的斜率部分“削平”为 1。
   • 操作：在堆中弹出最大的元素，直到堆的大小满足斜率要求（代码中通过 pop 实现）。
2. 区间平移：设修正后函数斜率为 0 的区间为 $[L, R]$。加上边权 $w$ 后，最优区间变为 $[L+w, R+w]$。
   • 操作：取出堆顶 $R$ 和次大值 $L$，将它们修改为 $R+w$ 和 $L+w$ 再放回堆中。

3. 代码详细解析

3.1 数据结构

struct node {
    int father;
    long long fa_w; // 连向父节点的边权
    int ch_cnt;     // 子节点个数（度数）
    priority_queue<long long, std::less<>, pairing_heap_tag> f; // 可并堆
};

这里使用了 pairing_heap_tag，其 join 操作的时间复杂度均摊为 $O(1)$，非常适合本题的合并操作。

3.2 变量 b 的含义

long long b = 0;
// ...
b += (tree[p].fa_w = w);

b 初始化为所有边权之和。 在 Slope Trick 中，堆维护的是函数的形状（转折点），而 $b$ 用于维护函数的截距（即 $f(0)$ 的值）。最终答案 $f_{root}(0)$ 可以通过 $b$ 减去堆中相关转折点的坐标得到。

3.3 核心循环（自底向上）

代码使用了一个反向循环 for (int p = n - 1; p > 0; --p)，这利用了题目输入的拓扑序（或者简单的节点编号特性），相当于后序遍历（从叶子到根）。

非叶子节点的处理：

if (p < n - m) { // 如果 p 不是叶子节点
    // 1. 斜率修正：保留斜率 <= 1 的部分
    // 堆的大小代表了斜率的变化量。如果有 ch_cnt 个孩子，斜率最大累加到 ch_cnt。
    // 我们需要弹出 ch_cnt - 1 个点，使得最右侧斜率变为 1。
    for (int _ = 1; _ < tree[p].ch_cnt; ++_) {
        tree[p].f.pop();
    }

    // 2. 取出最优区间 [L, R]
    l = tree[p].f.top(); tree[p].f.pop();
    r = tree[p].f.top(); tree[p].f.pop();
}

边的延伸（平移）：

// 3. 区间平移 [L, R] -> [L+w, R+w]
// 注意：对于叶子节点，初始 L=0, R=0，直接 push(0+w, 0+w)
tree[p].f.push(l + tree[p].fa_w);
tree[p].f.push(r + tree[p].fa_w);

// 4. 合并到父节点
tree[tree[p].father].f.join(tree[p].f);

3.4 根节点的处理与答案计算

// 根节点不需要向父节点延伸，也不受边权限制，只受斜率限制
// 根节点的斜率最终应该修正为 0（因为 x 可以取任意大，不需要 slope=1 的增长）
// 实际上题目要求所有叶子深度相同，等价于求 min(f_root(x))
for (int _ = 0; _ < tree[0].ch_cnt; ++_) {
    tree[0].f.pop(); // 修正斜率
}

// 计算 f(0)。
// 根据 Slope Trick 的性质，f(0) = Sum(All Edges) - Sum(Points in Heap where slope < 0)
// 这里利用了数学推导：b 初始为边权和，不断减去堆顶元素直到堆空，实际上是在计算截距。
while (!tree[0].f.empty()) {
    b -= tree[0].f.top();
    tree[0].f.pop();
}

4. 复杂度分析

• 时间复杂度：$O((N+M) \log (N+M))$。
  • 每个节点都会进行 join 操作，配对堆合并是 $O(1)$ 的。
  • 每个转折点最多进堆一次、出堆一次。虽然 pop 操作最坏是 $O(\log N)$，但均摊下来非常快。
• 空间复杂度：$O(N+M)$，用于存储树结构和堆节点。

5. 总结

这段代码是解决 APIO 2016 烟花表演的标准解法。它巧妙地利用了 DP 函数的凸性，通过可并堆维护斜率转折点，避免了繁琐的函数维护，将问题转化为堆的合并、弹出和插入操作，极其高效。

关键点回顾：

1. Pairing Heap：用于快速合并子树信息。
2. Pop Loop：ch_cnt - 1 次弹出是为了将子树合并后的最大斜率限制回 1（对应边的物理约束）。
3. Push L+w, R+w：对应最优区间的平移和拐点的变化。
4. 最终答案：通过边权总和减去堆中剩余元素计算得出。