官方题解最后是3^n，可以加以优化。

题解最后有一步枚举非叶子集合及其超集。

但注意对于一个确定的非叶子集合，枚举的叶子贡献的方案数是独立的。

所以不需要枚举超集，只需要知道选了奇数或偶数个叶子的总方案数。于是这一部分复杂度就从$3^n$变成$n2^n$。

还有一个部分是计算给定点集的生成基环树的方案数。

这部分题解有所提及，“我们考虑有向图中的基环外向树可以看成就是每一个点恰好连出去一条边”“答案似乎是度数的乘积”。

这样有两个问题：1.这样算出来的是基环外向树森林的个数，而不是树；2.因为是无向边，所以可能有相邻的两个点选中了同一条边。

第一个问题，可以通过集合幂级数求ln来解决，复杂度$n^22^n$。

第二个问题，多算的方案，等价于从一棵生成树上选中一条边成为重边，方案数即为生成树个数*（点数-1），复杂度$n^32^n$

最后总复杂度就是$n^32^n$，比题解的$3^n$要优越，跑得也更快。

提交记录