【昆明之前每天补一道区域赛银/铜牌题】2021上海 G-Edge Groups(树形dp+数学)

题意：有n-1条边(保证为偶数)，分成n-1/2组，每组俩条边，且这俩条边之间要有一个公共点，求方案数

解析：我们想到用f[i]代表以i为根的方案数，那么f[i]首先要先乘以v:g[i],f[i]=f[i]*f[v],考虑子方案数的求法

假设当前我们有n条可以自由组合的边，若n为偶数 那么答案要再乘以一个C(n,2)C(n-2,2)....*C(2,2) / A(n/2,n/2)

化简这个式子，得到原式=n!/n!! = 1 *3 *5 *...(n-1)

若n为奇数，那么其中一定有一条边是要贡献给其父亲结点的，因为题目保证了边数是偶数，不可能会有奇数的边剩下。

所以我们需要统计对于每个根，其可以自由组合的边有多少条，这个很简单，如果对于子树的某一个节点，其可以自由组合的边数是偶数，那么与其父亲相连的边就可以参与自由组合，反之就不能。这个是很好统计计算的，综上所述就可以得到本题代码了。

反思，自己在写的时候不知道双阶乘的公式，在处理化简式子的时候卡了很久，牢记n!*2^n=(2n)!!

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define INF 0x3f3f3f3f
#define rep(j, a, b) for(int i=a;i<=b;i++)
#define per(j, a, b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=1e5+5;
const ll mod=998244353;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}

vector<int>g[maxn];

ll f[maxn];

ll dfs(int u,int fa)
{
    ll cnt=0;
    f[u]=1;
    for(auto v:g[u])
    {
        if(v==fa) continue;
        //if(g[v].size()&1) cnt++;
        if(!dfs(v,u)) cnt++;
        f[u]=(f[u]%mod*f[v]%mod)%mod;
    }
    for(int i=1;i<=cnt;i+=2) f[u]=(f[u]%mod*i%mod)%mod;
    return (cnt%2)?1:0;//对于子树的某一个节点，其可以自由组合的边数是偶数，那么与其父亲相连的边就可以参与自由组合，反之就不能
}

signed main()
{
    int n=read();
    rep(i,1,n-1)
    {
        int u=read(),v=read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    printf("%lld\n",f[1]%mod);
}