P14902 题解

albertting · 2026-10-22 14:03:31 · 题解

经典结论题。

一棵树上，设 S_1,\dots,S_k 按 \operatorname{dfn} 排列，令 S_{k+1}=S_1，记

其中 D=2|E(T_S)|，其中 T_S 是包含 S 的最小连通子树，E(T_S) 表示子树 T_S 包含的边数。

用 std::set 维护每个颜色的点集是容易的，主要关心证明。

主要需要证明的是 D=2|E(T_S)|。

任取树边 e，删去后树分成两侧 A,B。

• 若 e\notin E(T_S)，则某一侧不含 S 里的点，所以环序列相邻点不可能跨过 e，贡献 0。
• 若 e\in E(T_S)，则两侧都含 S 里的点。由 \operatorname{dfn} 序的性质，这一侧中的点在 S_1,\dots,S_k 中形成连续区间。于是环序列 S_1,S_2,\dots,S_k,S_1 中，这个连续区间和补集之间恰好有两个交界，所以边 e 被相邻点路径跨过恰好 2 次，贡献 2。

因此 D=\sum_{e\in E(T_S)}2=2|E(T_S)|。