昨晚管神讲太晚了所以咕到8.8来写了
上午博弈论和杂题，依旧听不懂?，离线了一个上午，下午又赫了一个下午，收获满满捏?
同时破 1000AC 了，为此 whr 特地发私信庆祝：
晚上管神讲组合数学、GF 和群论，真抽象捏，再次离线喽?。反正明天都放假了，直接开摆！
推歌部分：
Lost Emotion feat. nomico - Masayoshi Minoshima/のみこ
秦心的歌也好好听??而且被sb616收录了??
P3687
我们考虑如果原图本身就不是一颗仙人掌，那无论如何都不可能是仙人掌。而如果原图中有环，那么这个环也不能被加入的边覆盖到，因为这样就不满足每个边只在一个简单环中的要求了。
因此整张图就被这些环分成了一堆部分，每个部分都是一颗树，并且每部分分开计算，因此我们就可以只考虑树的情况。
由于仙人掌中的割边不利于我们dp，我们强制让割边都连一条重边，这样就好dp了。我们设 \(f_i\) 为子树内加边的方案，\(g_i\) 为往上扩展一条边的方案。为了方便转移，再设 \(h_i\) 为有 \(i\) 个儿子时子树内连边的方案数。
首先 \(h_i\) 的递推式很容易计算，我们只需考虑最后一条边是和父亲连还是子树内再找一个来配对，因此
\[h_i=h_{i-1}+(i-1)h_{i-2}
\]
我们再考虑 \(f\) 和 \(g\) 的转移方程。
我们记 \(ch\) 为儿子的个数，每个子节点向上连边是独立的，而这些子节点又是可以互相连边的，因此 \(f\) 的方程为：
\[f_{u}=h_{ch}\times \prod \limits _{v\in son_u} g_v
\]
再考虑 \(g\) 的方程，首先 \(u\) 本身可以直接向上扩展，或者是从子节点中选出一个点向上扩展，这时剩下的点其实也不影响，也可以向上扩展到 \(u\)，或者内部自己连边，因此转移方程为：
\[g_u=f_u+h_{ch-1}\times ch\times \prod \limits _{v\in son_u} g_v
\]
时间复杂度 \(O(n)\)。
偷看姐姐图片的恋恋