题目描述
题目大意
给出一个点数为n的树（n为奇数），将n-1条边两两分组。每组内需要满足：有两条边，且这两条边要有一个公共点。
题目分析
通 过 找 规 律 我 们 可 以 发 现 ： 对 于 以 u 为 根 的 树 和 它 的 子 节 点 v ， 如 果 v 子 树 可 以 匹 配 边 数 为 偶 数 ， 那 么 u − v 这 条 边 通过找规律我们可以发现：对于以u为根的树和它的子节点v，如果v子树可以匹配边数为偶数，那么u-v这条边 通过找规律我们可以发现：对于以u为根的树和它的子节点v，如果v子树可以匹配边数为偶数，那么u−v这条边 对 于 u 树 来 说 就 是 可 用 的 。 如 果 v 子 树 可 以 匹 配 的 边 数 为 奇 数 ， 那 么 v 子 树 匹 配 完 后 会 剩 下 一 条 边 ， 而 能 与 这 条 剩 对于u树来说就是可用的。如果v子树可以匹配的边数为奇数，那么v子树匹配完后会剩下一条边，而能与这条剩 对于u树来说就是可用的。如果v子树可以匹配的边数为奇数，那么v子树匹配完后会剩下一条边，而能与这条剩 边 能 匹 配 的 只 有 u − v 边 ， 因 此 u − v 边 对 于 u 子 树 来 说 即 为 不 可 用 的 边 。 边能匹配的只有u-v边，因此u-v边对于u子树来说即为不可用的边。 边能匹配的只有u−v边，因此u−v边对于u子树来说即为不可用的边。
而
对
于
一
棵
树
的
可
用
边
来
说
，
对
其
两
两
分
组
的
方
案
是
为
(
设
边
数
为
n
且
n
为
偶
数
)
：
而对于一棵树的可用边来说，对其两两分组的方案是为(设边数为n且n为偶数)：
而对于一棵树的可用边来说，对其两两分组的方案是为(设边数为n且n为偶数)：
C
2
2
∗
C
4
2
∗
…
∗
C
n
−
2
2
∗
C
n
2
(
n
/
2
)
!
\frac{C_2^2*C_4^2*…*C_{n-2}^2*C_n^2}{(n/2)!}
(n/2)!C22∗C42∗…∗Cn−22∗Cn2
经
过
化
简
后
可
以
得
到
：
经过化简后可以得到：
经过化简后可以得到：
1
∗
3
∗
…
∗
(
n
−
3
)
∗
(
n
−
1
)
1*3*…*(n-3)*(n-1)
1∗3∗…∗(n−3)∗(n−1)
这 样 就 能 通 过 可 供 使 用 的 边 数 来 求 出 方 案 数 。 然 后 我 们 再 来 看 如 何 求 出 一 棵 树 中 可 供 使 用 的 边 数 ： 这样就能通过可供使用的边数来求出方案数。然后我们再来看如何求出一棵树中可供使用的边数： 这样就能通过可供使用的边数来求出方案数。然后我们再来看如何求出一棵树中可供使用的边数：
对
于
一
棵
树
u
，
存
在
u
的
一
棵
子
树
v
，
如
果
v
中
可
供
使
用
的
边
为
奇
数
，
那
么
就
需
要
占
用
u
−
v
边
，
所
以
v
没
有
对
u
贡
献
可
对于一棵树u，存在u的一棵子树v，如果v中可供使用的边为奇数，那么就需要占用u-v边，所以v没有对u贡献可
对于一棵树u，存在u的一棵子树v，如果v中可供使用的边为奇数，那么就需要占用u−v边，所以v没有对u贡献可
使
用
的
边
。
（
v
中
可
使
用
的
边
不
属
于
u
）
使用的边。（v中可使用的边不属于u）
使用的边。（v中可使用的边不属于u）
否
则
，
v
中
可
使
用
的
边
数
为
偶
，
就
不
会
占
用
u
−
v
边
，
此
时
v
就
可
以
贡
献
一
条
可
用
的
边
。
否则，v中可使用的边数为偶，就不会占用u-v边，此时v就可以贡献一条可用的边。
否则，v中可使用的边数为偶，就不会占用u−v边，此时v就可以贡献一条可用的边。
我
们
按
照
上
述
的
规
则
，
用
树
形
d
p
求
解
即
可
。
我们按照上述的规则，用树形dp求解即可。
我们按照上述的规则，用树形dp求解即可。
状
态
表
示
：
f
[
u
]
为
以
u
为
根
的
子
树
，
能
够
匹
配
的
方
案
数
为
多
少
。
状态表示：f[u]为以u为根的子树，能够匹配的方案数为多少。
状态表示：f[u]为以u为根的子树，能够匹配的方案数为多少。
状
态
转
移
：
直
接
通
过
乘
法
原
理
合
并
u
树
和
其
子
树
v
的
贡
献
即
可
。
状态转移：直接通过乘法原理合并u树和其子树v的贡献即可。
状态转移：直接通过乘法原理合并u树和其子树v的贡献即可。
代码如下
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
#include <iomanip>
#define LL long long
#define ULL unsigned long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PDD pair<double,double>
#define x first
#define y second
using namespace std;
const int N=1e5+5,mod=998244353;
vector<int> h[N];
int f[N];
bool dfs(int u,int fa) //dfs，返回值为此树的可用边数是否为奇数
{
f[u]=1;
int cnt=0; //cnt记录本树可用的边数
for(int v:h[u])
{
if(v==fa) continue;
if(!dfs(v,u)) cnt++;
f[u]=(LL)f[u]*f[v]%mod; //合并u与v树的方案数（乘法原理）
}
for(int i=1;i<=cnt;i+=2) f[u]=(LL)f[u]*i%mod; //利用分析中的公式直接计算方案数即可
return cnt&1;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<n;i++) //建树
{
int u,v;
cin>>u>>v;
h[u].push_back(v);
h[v].push_back(u);
}
dfs(1,-1);
cout<<f[1]<<endl;
return 0;
}