自动搬运

查看原文

来自洛谷，原作者为

	KaguyaH 嘛。

搬运于2025-08-24 22:37:45，当前版本为作者最后更新于2022-04-19 21:57:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Problem Statement

给定 $n$ 个点的二叉树，点有权值 $d_{1 \dots n}$。需要依次删除所有边。删边代价为两端点权值和；删边前会交换两端点权值。求最小总代价。

Constraints

$1 \le n \le 5 \times 10^3, 1 \le d_i \le 10^9$。

Solution

Changelog: 修正了部分笔误，提供了避免斜率优化的做法。

记 $S_r$ 表示以 $r$ 为根的子树。认为点权是在树上移动的。

设 $f_{u, v}$ 表示 $S_{\operatorname{lca}(u, v)}$ 中，将 $d_u$ 移出，移入的点权最终停留在 $v$，删去子树中所有边以及 $\operatorname{lca}(u, v)$ 入边的最小总代价（不包括换入的点权）。

按 $r = \operatorname{lca}(u, v)$ 自下而上的顺序转移。下文中「朴素转移」意为枚举所有合法转移。下文 $d$ 可能表示节点，但不会造成歧义，请注意区分。由于公式较多，有可能出现笔误。

• 若 $\deg r = 0$：$f_{r, r} = d_r$。

• 若 $\deg r = 1$：

  • 记 $d$ 为 $r$ 的孩子。
  • 若 $u = r$：$f_{u, v} = \min \lbrace d_u + f_{w, v} \rbrace \pod { \operatorname{lca}(v, w) = d }$。枚举 $v, w$，总时间复杂度 $O(n^2)$。
  • 若 $v = r$：$f_{u, v} = \min \lbrace f_{u, w} + d_u + d_v(\operatorname{dep}_w - \operatorname{dep}_v) \rbrace \pod {\operatorname{lca}(u, w) = d}$。枚举 $u, w$，总时间复杂度 $O(n^2)$。

• 若 $\deg r = 2$：

  • 若 $u = r$：

    记 $d$ 为 $r$ 在 $v$ 一侧的孩子，$d'$ 为另一侧的孩子。易知：应先删掉 $r$ 的入边；再删掉 $r \to d$ 的边；再删掉 $r \to d'$ 的边。

    枚举 $w$ 使得 $d_w$ 由 $S_d$ 移至 $S_{d'}$；枚举 $x$ 由 $S_{d'}$ 移至 $r$；枚举 $d_w$ 移至的点 $y$；则有：

    $$\begin{aligned} f_{u, v} &= \min_{w, x, y} \lbrace d_u + f_{w, v} + f_{x, y} + d_w({\operatorname{dep}}_y - {\operatorname{dep}}_u) \rbrace \cr &= d_u + \min_{y} \lbrace \min_x f_{x, y} + \min_w \lbrace ({\operatorname{dep}}_y - {\operatorname{dep}}_u) \cdot d_w + f_{w, v} \rbrace \rbrace \cr &= d_u + \min_w \lbrace f_{w, v} + \min_y \lbrace (\operatorname{dep}_y - \operatorname{dep}_u) \cdot d_w + \min_x f_{x, y} \rbrace \rbrace \end{aligned} \pod{ \operatorname{lca}(v, w) = d, \operatorname{lca}(x, y) = d'} $$

    按照第二行的式子，发现 $v$ 确定时第二层大括号内部形如一个关于 $\operatorname{dep}_y - \operatorname{dep}_u$ 的一次函数。可以斜率优化。枚举 $w$ 预处理；枚举 $y$ 转移；总时间复杂度 $O(n^2)$。

    此外，若按照第三行的式子，发现第三层 $\min$ 仅与 $y$ 有关，第二层 $\min$ 仅与 $w$ 有关；可以枚举 $y, x$ 预处理每个 $y$ 对应的第三层的值，枚举 $w, y$ 预处理每个 $w$ 对应的第二层的值，枚举 $v, w$ 进行转移，即可避免斜率优化。总时间复杂度 $O(n^2)$。

  • 若 $v = r$：

    记 $d$ 为 $r$ 在 $u$ 一侧的孩子，$d'$ 为另一侧的孩子。易知：应先删掉 $r \to d'$ 的边；再删掉 $r \to d$ 的边；再删掉 $r$ 的入边。

    枚举 $w$ 使得 $d_w$ 由 $S_{d'}$ 移至 $S_d$；枚举 $d_r$ 移至的点 $x$；枚举 $d_w$ 移至的点 $y$；则有：

    $$\begin{aligned} f_{u, v} &= \min_{w, x, y} \lbrace f_{w, x} + d_v(\operatorname{dep}_x - \operatorname{dep}_v) + f_{u, y} + d_w(\operatorname{dep}_y - \operatorname{dep}_v) + d_u \rbrace\cr &= d_u + \min_y \lbrace f_{u, y} + \min_w \lbrace d_w (\operatorname{dep}_y - \operatorname{dep}_v) + \min_x \lbrace f_{w, x} + d_v (\operatorname{dep}_x - \operatorname{dep}_v) \rbrace \rbrace \rbrace \end{aligned} \pod{\operatorname{lca}(w, x) = d', \operatorname{lca}(u, y) = d} $$

    发现第二层 $\min$ 与 $u$ 无关，第三层 $\min$ 与 $y$ 无关。枚举 $w, x$ 预处理；枚举 $y, w$ 预处理；枚举 $u, y$ 转移；总时间复杂度 $O(n^2)$。

  • 若 $u \ne r, v \ne r$：

    记 $d$ 为 $r$ 在 $u$ 一侧的孩子，$d'$ 为 $r$ 在 $v$ 一侧的孩子。易知：应先删掉 $r \to d$ 的边；再删掉 $r$ 的入边；再删掉 $r \to d'$ 的边。

    枚举 $d_r$ 移至的点 $w$；枚举 $x$ 使得 $d_x$ 由 $S_{d'}$ 移至 $r$；则有：

    $$f_{u, v} = \min_{w, x} \lbrace f_{u, w} + d_r (\operatorname{dep}_w - \operatorname{dep}_r) + d_u + f_{x, v} \rbrace \pod{ \operatorname{lca}(u, w) = d, \operatorname{lca}(v, x) = d' } $$

    枚举 $u, w$ 预处理；枚举 $u, v$ 转移；总时间复杂度 $O(n^2)$。

时空复杂度 $O(n^2)$。