重点在于转化“最大匹配唯一”的限制。发现它等价于树是孤点或最大匹配是完美匹配。显然最大匹配若不完美则容易调整出多个最大匹配。若最大匹配完美考虑反证法假设存在多个完美匹配对比任意一对都能找到环矛盾。然后设 ,0/1/2fu,0/1/2​ 分别为 u 和父亲匹配、和儿子匹配、作为孤点时 u 子树的删边方案数。设 u 的儿子集合为 sonu​。转移方程如下。,0∏∈(2,1,2)fu,0​v∈sonu​∏​(2fv,1​fv,2​),1(∏∈(2,1,2))⋅(∑∈,02,1,2)fu,1​(v∈sonu​∏​(2fv,1​fv,2​))⋅(v∈sumu​∑​2fv,1​fv,2​fv,0​​),2∏∈(,1,2)fu,2​v∈sonu​∏​(fv,1​fv,2​)其中 ,1fu,1​ 的计算可以使用前缀和技巧避免求逆元具体实现见代码。时间复杂度 ()O(n)。#include bits/stdc.h #define rep(i,a,b) for(int i(a);ib;i) #define rept(i,a,b) for(int i(a);ib;i) #define eb emplace_back #define int long long using namespace std; constexpr int P998244353,N3e55; int n,u,v,f[N][3]; vectorint g[N]; // f[i][0]i的子树i和fa[i]匹配的方案数 // f[i][1]i的子树i和i的一个儿子匹配的方案数 // f[i][2]i的子树i孤立的方案数 void dfs(int u,int pre){ f[u][0]f[u][2]1; f[u][1]0; int t1; for(int v:g[u]){ if(vpre) continue; dfs(v,u); (f[u][0]*f[v][1]*2f[v][2])%P; f[u][1](f[u][1]*(f[v][1]*2f[v][2])t*f[v][0])%P; (t*f[v][1]*2f[v][2])%P; (f[u][2]*f[v][1]f[v][2])%P; } } signed main(){ cin.tie(0)-sync_with_stdio(0); cinn; rep(i,1,n){ cinuv; g[u].eb(v),g[v].eb(u); } dfs(1,0); cout(f[1][1]f[1][2])%P; cerr1000.0*clock()/CLOCKS_PER_SECmsendl; return 0; }