# 心灵支配树 题解

## 解法与取舍

**出题人解法：轻子树清空、重子树保留与根路径并集。** 根路径并集方案作为标程，测量中的峰值内存较低。环距离和方案在部分树形上较快，两者具有相同的渐进时间与空间界，作为并列方案。两份实现均使用显式遍历和 64 位权值。

**程序与署名：** [std.cpp](std.cpp) 实现出题人解法；Codex（GPT-6）负责实现整理、边界处理与证明说明。Codex（GPT-6）采用的小并大集合与 DFS 序环距离和见 [alternative.cpp](alternative.cpp) 和[并列方案题解](solution-alternative.zh.md)。

## 最小连接子树

对支配子树 $u$ ，令 $S$ 为其中各节点控制的目标集合。所有目标汇合所走的路径必须包含连接 $S$ 的最小子树 $H$ ；在 $H$ 内选汇合点即可达到这个下界。点权为正，已控制点无需付费，因此答案为 $H$ 的点权和减去 $S$ 的点权和。

## 按 DFS 序插入根路径

在目标所在树中，以 $1$ 为根，令 $d_x$ 为根到 $x$ 的点权和但不包含根权。用有序集合保存 $S$ 的 DFS 进入序。维护所有根到目标路径的并集点权和，再减去已选目标权值，记为 $W$ ；同时维护总最近公共祖先 $g$ .

空集合插入 $x$ 时，$W=d_x+v_1-v_x$ .非空时，找 $x$ 的循环前驱、后继 $a,b$ ，令 $z$ 为 $\operatorname{LCA}(a,x)$ 与 $\operatorname{LCA}(b,x)$ 中较深者，则

$$W\leftarrow W+d_x-d_z-v_x.$$

为什么 $z$ 是新根路径与已有并集的最深交点？某祖先的子树在 DFS 序中是连续区间；若该区间包含其他已选点，那么在按序寻找 $x$ 的邻居时，至少有一个邻居仍在这个区间。因此所有已选点与 $x$ 的最深 LCA 必在两个邻居中取得。新增的路径只有 $z$ 以下部分；再扣掉新控制点自身的费用即得公式。即使 $x$ 已经位于旧并集里，新增部分为零，仍须扣掉它转为受控制点后的费用。

令 $g\leftarrow\operatorname{LCA}(g,x)$ .根路径并集比最小连接子树多出根到 $g$ 但不含 $g$ 的部分，其权值为 $d_g+v_1-v_g$ .所以

$$\operatorname{answer}=W-d_g-v_1+v_g.$$

## 保留重子树

先计算支配树子树大小和最大孩子。处理节点时，依次递归意义上处理所有轻孩子并清空临时集合，再处理重孩子并保留集合，最后插入当前目标以及各轻子树的全部目标。此时集合恰为 $S$ ，读取上述答案。若本次调用不要求保留，则清空集合。

程序用带阶段与保留标志的显式任务栈实现这个顺序。轻子树的节点通过 DFS 序连续区间枚举；控制映射是排列，故同一集合中没有重复目标。

## 正确性与复杂度

插入公式精确保持根路径并集及已控制费用，总 LCA 修正精确移除无须经过的公共前缀。重子树保留只改变计算顺序，不改变每次读答案时的目标集合，故各节点答案正确。

每个元素因轻边而被重新插入的次数至多 $O(\log(n+1))$ .每次有序集合插入与倍增 LCA 查询为 $O(\log(n+1))$ ，总时间 $O(n\log^2(n+1))$ .有序集合和遍历状态为 $O(n)$ ，加上 LCA 表，总空间 $O(n\log(n+1))$ .清空集合的总成本计入相应插入次数。

## 验证与性能

各方案的五次重复计时与峰值内存记录见[评测环境与性能](../../../docs/评测环境与性能.md)。