题目
传送门 to luogu
思路
只有一种最大匹配？这咋整？这能表示到状态里面吗？
最大匹配当然往增广路径方面想。而且，匹配不仅最大，而且唯一，这对增广路径的限制很强！
我们一般的增广路径都是这样的：从未匹配的点出发，未匹配边 匹配边 未匹配边 匹配边 未匹配边，在未匹配的点结束。这样会使匹配数增大一。不过我们还需要让最大匹配唯一，所以我们可以去掉最后一条未匹配边。即：从未匹配点出发，匹配边、未匹配边交替出现，走偶数条边 的路径也是不被允许的。可是 走奇数条边 就是增广路径了，也是不被允许的！唯一的可能：走零条边。
得出了结论：一个未匹配的点没有相邻的点。
于是可以树形 了。分成三种情况：
- 已经与某个儿子匹配。
- 没有跟某个儿子匹配，非孤身一人。
- 没有任何一条边与之相连。
依次记为
。转移很简单，分别列举一下吧。增加文章长度。
对于 ：
- 以前已经匹配。新的儿子也已经匹配，二者可连或不连；新的儿子膝下无子，二人断绝父子关系。
- 以前没有匹配（是否孤身一人无所谓）。新的儿子没有匹配或者膝下无子，必须连边。
对于 ：
- 以前就非孤身一人。新的儿子匹配完成，可选连边或不连；新的儿子膝下无子，必须不连。
- 以前一直孤身一人。新的儿子匹配完成，必须连边。
对于 ：
- 以前一直是空巢老人。新的儿子要么是膝下无子，断绝父子关系；要么是匹配完成，仍然不能连边。
初始状态自然是无子。时间复杂度 。
代码
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
inline int readint(){int a = 0; char c = getchar(), f = 1;for(; c<'0'||c>'9'; c=getchar())if(c == '-') f = -f;for(; '0'<=c&&c<='9'; c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}
inline void writeint(long long x){if(x < 0) putchar('-'), x = -x;if(x > 9) writeint(x/10);putchar((x%10)^48);
}
template < class T >
void getMax(T&a,T b){ if(a < b) a = b; }
template < class T >
void getMin(T&a,T b){ if(b < a) a = b; }const int MaxN = 300005;
struct Edge{int to, nxt;Edge(int T=0,int N=0){to = T, nxt = N;}
} edge[MaxN<<1];
int head[MaxN], cntEdge, n;
void addEdge(int a,int b){edge[cntEdge] = Edge(b,head[a]);head[a] = cntEdge ++;edge[cntEdge] = Edge(a,head[b]);head[b] = cntEdge ++;
}const int Mod = 998244353;
// 0:已经匹配完成（所以有子）
// 1:没有匹配，有子
// 2:孤零零一个人
int dp[MaxN][3];int tmp[3]; // dp转移辅助数组
void dfs(int x,int pre){dp[x][2] = 1; // 一开始无子for(int i=head[x],y; ~i; i=edge[i].nxt){if(edge[i].to == pre) continue;dfs(y = edge[i].to,x);tmp[0] = 1ll*(dp[x][1]+dp[x][2])*(dp[y][1]+dp[y][2])%Mod;tmp[0] = (tmp[0]+dp[x][0]*(dp[y][0]*2ll+dp[y][2]))%Mod;tmp[1] = (1ll*dp[x][2]*dp[y][0]%Mod+dp[x][1]*(2ll*dp[y][0]+dp[y][2]))%Mod;tmp[2] = 1ll*dp[x][2]*(dp[y][0]+dp[y][2])%Mod;for(int j=0; j<3; ++j) dp[x][j] = tmp[j];}
}int main(){int n = readint();for(int i=1; i<=n; ++i) head[i] = -1;for(int i=1; i<n; ++i)addEdge(readint(),readint());dfs(1,-1); int ans = dp[1][0];ans = (ans+dp[1][2])%Mod;printf("%d\n",ans);return 0;
}