CF1032F Vasya and Maximum Matching 题解
重点在于转化“最大匹配唯一”的限制。发现它等价于树是孤点或最大匹配是完美匹配。显然，最大匹配若不完美则容易调整出多个最大匹配。若最大匹配完美，考虑反证法，假设存在多个完美匹配，对比任意一对都能找到环，矛盾。
然后设 \(f_{u,0/1/2}\) 分别为 \(u\) 和父亲匹配、和儿子匹配、作为孤点时 \(u\) 子树的删边方案数。
设 \(u\) 的儿子集合为 \(son_u\)。转移方程如下。
\
\
\
其中 \(f_{u,1}\) 的计算可以使用前缀和技巧避免求逆元，具体实现见代码。时间复杂度 \(O(n)\)。
#include #define rep(i,a,b) for(int i(a);i>n; rep(i,1,n){ cin>>u>>v; g.eb(v),g.eb(u); } dfs(1,0); cout 收藏一下 不知道什么时候能用到 分享、互助 让互联网精神温暖你我 yyds。多谢分享 前排留名，哈哈哈 用心讨论，共获提升！ 感谢分享，下载保存了，貌似很强大 新版吗？好像是停更了吧。 不错，里面软件多更新就更好了 yyds。多谢分享 不错，里面软件多更新就更好了 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 这个好，看起来很实用 谢谢分享，辛苦了
页:
[1]