心灵支配树 题解¶
解法与取舍¶
出题人解法：轻子树清空、重子树保留与根路径并集。 根路径并集方案作为标程，测量中的峰值内存较低。环距离和方案在部分树形上较快，两者具有相同的渐进时间与空间界，作为并列方案。两份实现均使用显式遍历和 64 位权值。
程序与署名： std.cpp 实现出题人解法；Codex（GPT-6）负责实现整理、边界处理与证明说明。Codex（GPT-6）采用的小并大集合与 DFS 序环距离和见 alternative.cpp 和并列方案题解。
最小连接子树¶
对支配子树 \(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)\) 中较深者，则
为什么 \(z\) 是新根路径与已有并集的最深交点？某祖先的子树在 DFS 序中是连续区间；若该区间包含其他已选点，那么在按序寻找 \(x\) 的邻居时，至少有一个邻居仍在这个区间。因此所有已选点与 \(x\) 的最深 LCA 必在两个邻居中取得。新增的路径只有 \(z\) 以下部分；再扣掉新控制点自身的费用即得公式。即使 \(x\) 已经位于旧并集里，新增部分为零，仍须扣掉它转为受控制点后的费用。
令 \(g\leftarrow\operatorname{LCA}(g,x)\) .根路径并集比最小连接子树多出根到 \(g\) 但不含 \(g\) 的部分，其权值为 \(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))\) .清空集合的总成本计入相应插入次数。
验证与性能¶
各方案的五次重复计时与峰值内存记录见评测环境与性能。