树形DP

Solution Ⅰ一道有点有趣的树形 $dp$ + 容斥，反正绕了我半天，这么神仙我也不可能写出来 首先考虑基本思路，直接求解恰好 $k$ 个较难，故考虑先求解大于等于 $k$ 的相似度的方案数，然后再容斥 考虑选定了必选的若干条边后计算方案数。显然此时整个图被分成了若干连通块，假设有 $k$ 个连通块，将连通块缩点，考虑它们可以组成的树的方案数，本来应该是 $k^{k - 2}$，然而对于每个连通块的缩点，它可以向其它连通块中包含的任意一点连接，也就是说，在 purfer 序列中，应当考虑连通块内的点编号在序列中的出现情况，而不是仅仅考虑连通块编号出现在序列中，故 prufer 序列中的每个位置可以填 $n$ 个数，即 $n^{k - 2}$，然而考虑了父亲，还需要考虑儿子，作为叶子节点的缩点后的连通块，同样的里面也是任意点向外连边，故还需乘上 $\prod size_i$，其中，$size_i$ 为连通块 $i$ 的大小，那么综上，对于一个存在 $k$ 个连通块的图，其构造的生成树的方案数为 $n^{k - 2} \times \prod size_i$ 那么现在考虑求解 $\p ...