题目大意

给定 $n$ 个 AI，它们之间连成一棵树。对每个节点 $i$，若删去它，则会分裂成 $d_i$ 个连通块，大小分别为：

求所有满足条件的树的数量对 $998244353$ 取模的结果。

题目解法

容易发现 $d_i$ 为 $i$ 节点的度数，那么肯定有：

这一步暂时先放着，待会儿用。

接下来设 $\exists i, j$，满足 $i$ 和 $j$ 有直接连边，那么：

• 当「删去 $i$」时，$j$ 所在连通块大小为 $c_{i, x}, 1 \le x \le d_i$。

• 当「删去 $j$」时，$i$ 所在连通块大小为 $c_{j, y}, 1 \le y \le d_j$。

在一棵树中，删除 $i$ 和删除 $j$ 得到的那两个「含有对方的连通块」实际上是互补的：它们加在一起正好包含整棵树的所有 $n$ 个节点，但由于「删点」各自去掉了 $i$ 或 $j$ 本身，所以这两个连通块在原图里其实是不重叠的。由此可得：

那么我们可以得到一个重要结论：若 $i$ 和 $j$ 相邻，则必存在一对 $\bigl(c_{i,x},\,c_{j,y}\bigr)$ 使它们之和等于 $n$。反之，若能在两个点的「子树大小多重集」里分别找到一对数之和为 $n$，就可以作为一条 $i$ 到 $j$ 的边。

我们把节点的所有 $c_{i, x}$ 收集在一起构成一个大小为 $\displaystyle\sum_{i = 1} ^ n d_i = 2(n - 1)$ 的多重集 $S$。树的每条边都会对应一对 $(k, n - k)$，此时我们得到「边的集合」，再确保第 $i$ 个点的度数为 $d_i$ 便可求出方案数。

问题：如何求出方案数？

我们先令 $\text{cnt}_x$ 为所有 $c_{i, x}$ 中连通块大小为 $x$ 的数量，$\text{mult}_{i, x}$ 为删除第 $i$ 个点时产生的连通块中大小为 $x$ 的连通块数量，考虑分为两步求解：

• 统计「纯粹的」方案数（不考虑重复）：

  • 当 $k \neq n - k$ 时，两者必须一一匹对，所以这里的方案数为 $\text{cnt}_k!$。因为题目保证有解，所以 $\text{cnt}_k$ 必然等于 $\text{cnt}_{n - k}$。
  • 当 $n \equiv 0 \pmod{2}$ 时，我们需要配对 $\displaystyle\frac{\text{cnt}_{\frac{n}{2}}}{2}$ 对 $\displaystyle(\frac{n}{2}, \frac{n}{2})$，设 $k = \displaystyle\frac{\text{cnt}_{\frac{n}{2}}}{2}$，那么此时的方案数为：

  $$k!! = \frac{k!}{2^{\frac{k}{2}}(\frac{k}{2})!}.$$

  这些式子相乘即可求出。

• 去除重复的方案：

  • 我们发现这个算法会重复计算。举个例子，比如 $\{2, 2, 3\}$，两个 $2$ 并无顺序可言，无论把「第 $1$ 个 $2$」匹配给邻居 $A$，把「第 $2$ 个 $2$」匹配给邻居 $B$，都对应一组同样的边 $\{(i, A), (i, B), (i, ?)\}$，只要这两个邻居在最终树中的度数信息等都吻合，就不能算作两种不同的树。
  • 为了避免这个问题，我们对于每个节点 $i$，将答案乘上 $\displaystyle\frac{1}{\text{mult}_{i, x}!}$ 即可。

综上，我们的答案可以表示为：

令 $M$ 为：

$$\left(\prod_{2k < n}\text{cnt}_k!\right) \times \begin{cases}(\frac{\text{cnt}_{\frac{n}{2}}}{2})!!, & n\text{ is even,}\\[6pt]1, & n\text{ is odd.}\end{cases} $$

令 $D$ 为：

$$\prod_{i = 1} ^ n \prod_{x}\left(\text{mult}_{i, x}!\right) $$

则答案为 $\displaystyle\frac{M}{D}$。

复杂度分析

• 时间复杂度：$O(n + \log P)$。

• 空间复杂度 $O(n)$。

代码实现

#include <bits/stdc++.h>

#define int long long

constexpr int N = 1e5 + 6, P = 998244353;

int power(int a, int b, int p) {
    int ans = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) {
            ans = ans * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> d(n + 1, 0);
    int sum = 0;
    std::vector<int> freq(n + 1, 0);
    std::vector<std::unordered_map<int, int>> cont(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> d[i];
        sum += d[i];
        for (int j = 1; j <= d[i]; ++j) {
            int sz;
            std::cin >> sz;
            ++freq[sz];
            ++cont[i][sz];
        }
    }
    int MAX = 2 * (n - 1);
    std::vector<int> fact(MAX + 1, 0), ifact(MAX + 1, 0);
    fact[0] = 1;
    for (int i = 1; i <= MAX; ++i) {
        fact[i] = fact[i - 1] * i % P;
    }
    ifact[MAX] = power(fact[MAX], P - 2, P);
    for (int i = MAX - 1; i >= 0; --i) {
        ifact[i] = ifact[i + 1] * (i + 1) % P;
    }
    int m = 1;
    for (int k = 1; k * 2 < n; ++k) {
        m = m * fact[freq[k]] % P;
    }
    auto so = [&](int x) -> int {
        int res = fact[x];
        res = res * power(power(2, x / 2, P), P - 2, P) % P;
        res = res * ifact[x / 2] % P;
        return res;
    };
    if (n % 2 == 0) {
        int x = freq[n / 2];
        m = m * so(x) % P;
    }
    int dd = 1;
    for (int i = 1; i <= n; ++i) {
        for (auto & kv : cont[i]) {
            dd = dd * fact[kv.second] % P;
        }
    }
    std::cout << m * power(dd, P - 2, P) % P;
}

int32_t main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0), std::cout.tie(0);

    int t;
    // std::cin >> t;
    t = 1;

    while (t--) {
        solve();
    }

    return 0;
}