【ICPC2021上海站】G题 Edge Groups 题解

题目大意

给定一棵有 $n$（$3 \le n \le 10^5$，$n$ 为奇数）个节点的树，将这 $n-1$ 条边两两分组，要求：分到同一组的边有相同的顶点。

求一共有多少种方法。结果对 $998244353$ 取模。

原题地址

思路

假设第一个节点是父节点，可以发现以下规律：

• 对于一个节点 $u$ 的子节点 $v$，如果 $v$ 的”可供使用”的边数（除去与 $u$ 相连的）为偶数，那么与 $u$ 相连的这条边对于 $u$ 来说，就是”可供使用”的了。（”可供使用”的意思就是可以与这个节点上的其它边结合）
• 对于一个节点 $u$ 的子节点 $v$，如果 $v$ 的”可供使用”的边数（除去与 $u$ 相连的）为奇数，那么与 $u$ 相连的这条边就要用来与 $v$ 相连的边组合，否则就无法成功分配。

那么对于每个节点可供使用的边，如果是偶数，那我们就两两分组；如果是奇数，那么我们留下与父节点相连的边，剩下的两两分组。

那么 $n$（$n$ 为偶数）个数两两分组的计算方式：

$$\frac{C_n^2 \cdot C_{n-2}^2 \cdots C_2^2}{A_{n/2}^{n/2}}$$

经过一番高强度化简之后得：

$$(n-1) \cdot (n-3) \cdots 3 \cdot 1$$

那么剩下就是解决可供使用的边的问题了，该如何计算呢？

这个”可供使用”的边是一个”递归”定义的，我们只看一个点和它的边，是没有办法看出来它哪些边是可以使用的，必须看它的子节点的可以使用的边，而它的子节点又和子节点的子节点有关系……

所以我们就用类似树形DP的方法，从根节点开始 dfs：

边界条件：叶子节点没有可供使用的边，所以也算偶数，那么它和父节点相连的这条边，就可以被父亲节点使用。

那么剩下的就一直按照最开始分析的计算即可。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const long long Mod = 998244353;
const int maxN = 1e5 + 7;

int n, d[maxN];
vector<int> e[maxN];
long long f[maxN];

bool dfs(int x, int fa)
{
    int cnt = 0;
    f[x] = 1;
    for(int i = 0; i < e[x].size(); ++i) {
        int y = e[x][i];
        if(y == fa)
            continue;
        if(!dfs(y, x))
            cnt++;
        f[x] = f[x] * f[y] % Mod;    
    }
    for(int i = 1; i <= cnt; i +=2)
        f[x] = f[x] * i % Mod;
    return cnt & 1;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, 0);
    printf("%lld\n", f[1]);
    return 0;
}