题解：CF2161F SubMST

BPG_ning · 2025-11-13 19:50:23 · 题解

接下来对于一个点集 S，对于在 S 的虚树上出现的所有点，x\notin S 是虚点，x\in S 是实点。

首先你会看错题，以为只需要求虚树大小，答案是 \sum_{i=2}^{n} (2^{\text{size}_i}-1)\times(2^{n-\text{size}_i}-1)，其中 \text{size}_i 表示以 1 为根的 i 的子树的大小。

但事实上不是这样的，因为那些虚树上的虚点不存在，所以不能直接用边连通。

我们考虑对于每个虚点算他额外的贡献。我们先定义对于虚点算哪些贡献：对于点集 S，把其生成树上的边放在原树上，删去我们已经计算过的虚树的边，会剩下若干条链，容易发现这些链的一段是虚点一段是实点，我们计算所有链头挂在这个虚点上的链的贡献。

对于一个虚点 x，设他在虚树上的度数为 d_x，根据定义 d_x\geq 3。考虑找到一个实点 u 满足 \text{dis}_{u,x} 最小，贡献为 (d_{x}-2)\times \text{dis}_{u,x}，即所有链都是 u\to x。

证明是容易但是繁琐的，这里不赘述。至于为什么是 d_x-2，因为 \text{dis}_{x,u} 已经算过一次，而且 x\to u 没有贡献。

接下来是简单的。枚举 x，\text{dis}=\sum_{i=1}[i\leq\text{dis}]，我们枚举 i，对于 x 的每个儿子统计出 \text{dep}\geq i 的数量。

把 d_{x}=0 和 d_{x}=1 的贡献单独算，d_{x}=2 不用管，因为 d_{x}-2=0。

把 -2 拿出来之后需要求 d_x\times 方案数，组合意义是钦定一个子树里面有实点的方案数，所以 =\sum_{y}(2^{\text{size}_y}-1)\times 2^{m-\text{size}_y}，其中 \text{size}_y 是我们统计的 \text{dep}\geq i 的数量，m 是其总数。

时间复杂度 O(n^2)。