题解：
好难的dp啊。。。看题解看了好久才看懂
http://blog.csdn.net/akak__ii/article/details/65935711
如果一开始的图就不是仙人掌，答案显然为0，可以Tarjan判断。 环显然不能产生贡献，所以可以把环边都断开。 现在模型转化为，给定一棵树，用路径去覆盖树上的每一条边，且路径不能相交，求方案数。 设fifi表示做完了ii的子树，且没有路径可以向上扩展。 设gigi表示做完了ii的子树，且有路径可以向上扩展。 设hihi表示有ii个点，它们之间匹配的方案数。 记numnum为点xx的儿子个数，那么显然 hi=hi−1+hi−2×(i−1) hi=hi−1+hi−2×(i−1) fx=Πgson×hnum fx=Πgson×hnum gx=fx+Πgson×hnum−1×num gx=fx+Πgson×hnum−1×num 简单解释一下： hihi转移的时候考虑当前第ii个儿子的选择，如果这个儿子不匹配，那就有hi−1hi−1种方案，如果匹配，那就可以和前面i−1i−1个儿子中的一个匹配，方案是(i−1)×hi−2(i−1)×hi−2 fxfx的转移：每个儿子都必须要可以往上扩，且各个儿子之间相对独立所以是ΠgsonΠgson，然后一共有hnumhnum种儿子的匹配方案，所以乘起来就是所有可能的方案。 gxgx的转移：首先xx自己可以往上扩展，方案就是fxfx，然后xx还可以选择一个儿子，记这个儿子为yy，匹配方案为gygy，那么剩下的儿子有Πson!=y gson×hnum−1Πson!=y gson×hnum−1种方案，乘起来就是Πgson×hnum−1Πgson×hnum−1由于yy的取值有numnum种选择所以还要乘上numnum。