题解：CF2161F SubMST

接下来对于一个点集 $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)$。