重点在于转化“最大匹配唯一”的限制。发现它等价于树是孤点或最大匹配是完美匹配。
显然，最大匹配若不完美则容易调整出多个最大匹配。若最大匹配完美，考虑反证法，假设存在多个完美匹配，对比任意一对都能找到环，矛盾。
然后设 \(f_{u,0/1/2}\) 分别为 \(u\) 和父亲匹配、和儿子匹配、作为孤点时 \(u\) 子树的删边方案数。
设 \(u\) 的儿子集合为 \(son_u\)。转移方程如下。
\[f_{u,0}=\prod_{v\in son_u}\left(2f_{v,1}+f_{v,2}\right)\]
\[f_{u,1}=\left(\prod_{v\in son_u}\left(2f_{v,1}+f_{v,2}\right)\right)\cdot\left(\sum_{v\in sum_u}\frac{f_{v,0}}{2f_{v,1}+f_{v,2}}\right)\]
\[f_{u,2}=\prod_{v\in son_u}\left(f_{v,1}+f_{v,2}\right)\]
其中 \(f_{u,1}\) 的计算可以使用前缀和技巧避免求逆元，具体实现见代码。时间复杂度 \(O(n)\)。
[code]#include #define rep(i,a,b) for(int i(a);i>n; rep(i,1,n){ cin>>u>>v; g.eb(v),g[v].eb(u); } dfs(1,0); cout |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
