题解：CF2161F SubMST

nullqtr_pwp · 2025-11-17 14:52:04 · 题解

对于 f(S)，可以枚举阈值 0\leq r<n，将所有 \text{dist}(u,v)\leq r 的连边，对答案计入连通块个数 -1 的贡献。对于连通块考虑钦定一个代表元，处理树的 bfs 序 bfn，那么取 bfn 最小的作为代表元。转化为每个点在多少 S 中成为代表元。限制即为，不存在 bfn 更小的点抢掉它的代表元地位。预处理 f_{u,i} 表示有多少 bfn_v<bfn_u,\text{dist}(u,v)=i，做一个前缀和即可。时间复杂度 \mathcal O(n^2)。

提交记录。