题意

给定 $n$ 个点的树 $T$ 和 $k$ 条额外边，求有多少种删 $\ge 0$ 条边的方法，使得剩下的图连通

$n\le 10^5,k\le 10$

分析

考虑 $n$ 很小的时候怎么做，这时可以用 胡策的统计 的做法，设原图连通子图的集合幂级数是 $f_S$ ，原图的子图的集合幂级数是 $g_S$ ，且 $f_{\emptyset}=g_{\emptyset}=0$ ，那么有 $g_S+1=\exp\left(f_S\right),f_{S}=\ln\left(1+g_S\right)$ ，子集 $\ln$ 即可

$n$ 很大的时候非常自然的想到虚树，这时图的点数是 $2k+(2k-1)\le39$ ，依旧太多了。

考虑虚树的建树过程，不断去掉度为 $1$ 的点，除非是钦定的虚树中的点，然后将度为 $2$ 的点缩起来，也就是将链缩点。

那么考虑直接对原图做这个过程，设剩下的图中有 $n_0$ 个点，$m_0$ 条边，那么由于边集除了额外边都是原树中的链缩成的边，所以 $m_0\le n_0-1+k$ ，又最小度大于等于 $3$ ，因此 $\dfrac{3n_0}{2}\le m_0$

所以 $n_0\le 2k-2 \le 18$ ，就可以用集合幂级数的做法了

但是原做法无法处理重边和缩完点的图，考虑集合幂级数的式子

设 $h\left(E\right)$ 表示断开 $E$ 中每条边的方案数 ，$r\left(E\right)$ 表示 $E$ 中边任意连的方案数

$$ \begin{aligned} g_S=&\sum_{T_1,T_2\cdots T_i\in S}\left[\bigcup_{j=1}^iT_j=S\right]\left[\forall 1\le j < k \le i,T_j\bigcap T_k=\emptyset\right]\prod_{j=1}^i f_{T_j} \\ & h\left(\bigcup_{1\le j<k\le i}\left\{\left(u,v\right)\mid\left(u,v\right)\in E, u\in T_j,v\in T_k\right\}\right)\cdot \dfrac{1}{i!} \\ g_S=&r\left(\left\{\left(u,v\right)\mid \left(u,v\right) \in E,u,v\in S\right\}\right) \end{aligned} $$

原问题中 $h\left(E\right)=1,r\left(S\right)=2^{\left|S\right| }$ ，因此可以直接 $\exp$

所以我们对于缩完链的图的每条边分别求出不连通和连通的方案数（合并两条边时不能同时断掉，否则就不可能连通了），分别为 $h_0\left(e\right),t_0\left(e\right)$

那么 $h\left(E\right)=\prod_{e\in E}h_0\left(e\right),r\left(S\right)=\prod_{e\in E} \left(h_0\left(e\right)+t_0\left(e\right)\right)$

那么令

$$ g^{\prime}_S=\dfrac{r\left(\left\{\left(u,v\right)\mid \left(u,v\right) \in E,u,v\in S\right\}\right)}{h\left(\left\{\left(u,v\right)\mid \left(u,v\right) \in E,u,v\in S\right\}\right)} $$

求 $f^{\prime}_S=\ln\left(g^{\prime}_S+1\right)$ 最后答案乘上 $h\left(E\right)$ 即可，这就等价于令每条边不连通的方案都是1，然后最后乘上对应的系数
时间复杂度 $\mathcal{O}\left(n\log_2n+k^22^{2k}\right)$

Code

实现写的有些问题，就不放了