心灵支配树：题解¶

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

最小连接子树¶

设受控制的节点集合为 \(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 位整数。