资讯详情

做法比官解复杂一点。

考虑固定一个 \(u\)，如何求出其最小覆盖时间。发现每次尽量使得每次覆盖点集扩展 \(2\)，但是有些地方会存在“卡住”所以只能扩展 \(1\)。所以与 Halls 定理类似的想法，考虑找到卡住的点 \(v\)（这里一定是割点/最远点），则其最小时间猜测为 \(\max_v n-sz_{u,v}+2ds_{u,v}\) 其中 \(ds_{u,v}\) 为最短路。

证明可以归纳法：若 \(v\) 不是最远点，则可以归纳成两个部分；否则可以一个点走 \(u \to v\)，另一个点根据最短路从小到大走即可。

然后放到圆方树考虑，由于是 \(\max\) 的 \(\max\)，考虑每个 \(v\) 其最远的 \(u\)。这里不难发现一个性质：\(ds_{u,v}\) 应该大于 \(sz_{u,v}\) 的一半。发现 “一半” 的条件所以考虑以重心 \(p\) 当根，然后考虑将 \(v\) 的贡献分成两个部分：

• \(u\) 是 \(v\) 子树内的点，所以可以直接树形 dp 求出最深点即可；
• \(u\) 是 \(v\) 子树外的点，由于是圆方树所以不能简单换根；但是因为与 \(p\) 为根，所以若 \(u,v\) 在 \(p\) 的同一棵子树，则显然不满足“一半”的性质，所以 \(u\) 一定在 \(p\) 子树外。于是一直延伸到点 \(p\)。首先若 \(p\) 是圆点则做完；若 \(p\) 为方点还是不能简单计算，但由于 “一半” 的性质，所以只能由最大的两棵子树到达，所以就做完了。

然后与官解的差距在于两点：

首先是计算答案，官解是由 \(ds\) 的变化量与覆盖点集的变化量考虑。其次就是计算 \(u\)，官解有一个发现就是每个点双，\(2ds_{u,v}-sz_{u,v}\) 的增量最多 \(1\)，所以直接考虑方点直径的一端为根，则 \(u\) 一定是 \(v\) 的祖先，于是直接换根就做完了。

复杂度都是 \(O(n)\)。