# 心灵支配树：题解

> 并列方案：小并大集合与 DFS 序环距离和。Codex（GPT-6）采用的解法，程序见 [alternative.cpp](alternative.cpp)；与出题人解法的比较见[主题解](solution.zh.md)。


## 最小连接子树

设受控制的节点集合为 $S$ .所有单位到同一地点的路线并集必须连通并包含 $S$ ，因而必须包含连接 $S$ 的最小子树 $H$ .取 $H$ 内任一点会合即可只使用 $H$ .由于点权为正，最优代价就是 $H$ 的点权和减去 $S$ 的点权和。

## 用 DFS 序维护子树权值

将每个非根节点 $x$ 的点权 $v_x$ 放到它与父亲之间的边上。令 $d(a,b)$ 为这种边权下的距离，$g$ 为 $S$ 中所有节点的最近公共祖先。子树 $H$ 的点权和等于其边权和加上 $v_g$ .

将 $S$ 按战场树的 DFS 进入次序循环排列为 $s_1,\ldots,s_t$ ，并令 $s_{t+1}=s_1$ .有

$$W(H)=\frac12\sum_{i=1}^{t}d(s_i,s_{i+1})+v_g$$

一条属于 $H$ 的边把选中节点分在两侧。DFS 序中，其中子树一侧的选中节点连续出现，所以循环相邻路线恰好跨过该边两次；不属于 $H$ 的边不会被跨过。这证明了公式，单节点集合也成立。

用有序集合保存 DFS 序。插入 $x$ 时，设其循环前驱、后继为 $a,b$ ，距离和增加

$$d(a,x)+d(x,b)-d(a,b)$$

同时累计受控制节点的点权和。集合中 DFS 序最小与最大的两个节点的最近公共祖先就是 $g$ ：每棵子树的 DFS 序连续，包含两端的最小祖先子树也包含其间全部选中节点。

## 合并与正确性

从叶到根计算每个支配子树的集合。保留最大孩子的有序集合，将其他孩子中的节点逐个插入，再插入 $e_u$ .孩子的集合与 $e_u$ 恰好组成 $S_u$ ，且排列保证没有重复节点。插入公式保持循环距离和正确，再减去受控制节点的点权和，即得到每个节点的最优代价。

## 复杂度与实现

每次把较小集合并入较大集合，元素所在集合大小至少翻倍，因此每个元素至多迁移 $O(\log n)$ 次。一次插入与倍增求最近公共祖先共需 $O(\log n)$ 时间，总时间 $O(n\log^2(n+1))$ ，空间 $O(n\log(n+1))$ .遍历使用显式栈和逆 DFS 序，不依赖树高对应的递归栈；距离和使用 64 位整数。