[Solution] SX2022 mis
KaguyaH
·
·
题解
Problem Statement
给定 n 个点的二叉树，点有权值 d_{1 \dots n}。需要依次删除所有边。删边代价为两端点权值和；删边前会交换两端点权值。求最小总代价。
Constraints
---
### 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)$。