题解：P7118 Galgame

· · 题解

题意

规定两棵无标号二叉树（可以为空）比较大小的方式如下：

  1. 相同形态的树大小相同。
  2. 如果节点个数不同，点数少的更小。
  3. 否则左子树不同时按照左子树比大小。
  4. 否则按照右子树比大小。

给定一棵 n 个节点的二叉树，求有多少棵无标号非空二叉树严格小于它。答案对 998244353 取模。n\le10^6。

思路

显然所有节点数 <n 的二叉树都是满足条件的，这部分二叉树一共有 \sum_{i=1}^{n-1}C_i 个，其中 C_i 表示卡特兰数第 i 项。而节点数 >n 的二叉树显然都不合法，现在考虑节点数恰好为 n 的所有二叉树。

令原树中 i 的子树大小为 siz(i)。先考虑根节点的情况，令根节点为 u，左右儿子分别为 l,r；那么对于左子树大小 <siz(l) 的二叉树也都是合法的，转化为开头的情况，但是还要算上右儿子的形态种数，于是此时对答案的贡献即为 \sum^{siz(l)-1}_{i=0}C_i\times C_{siz(u)-i+1}。然后考虑按照限制递归下去，若递归到左子树就表示以左子树的大小为标准，与右子树的形态无关，于是在左子树中计算得到的答案都要乘上 C_{siz(r)} 的系数；若递归到右子树就表示以右子树的大小为标准，意味着左子树形态已经固定，于是直接递归到右儿子中进行处理即可。

但这样复杂度是 O(n^2) 的，考虑一棵“左偏”的二叉树，即左子树大小级别为 O(n)，每次按照左子树大小计算贡献显然会被卡满。于是我们考虑当左子树大小大于右子树时，使用右子树的大小计算答案。对于节点 u，以它为根的二叉树一共有 C_{siz(u)} 个，正难则反，比原树小的二叉树相当于总方案数减去不比原树小的二叉树。于是当用右子树的大小计算贡献时，贡献即为 C_{siz(u)}-\sum^{siz(r)}_{i=0}C_i\times C_{siz(r)-i-1}。这样我们每一轮贡献至多计算 siz(u)/2 次轮，而随着深度增加子树的大小以对数级别下降，于是总复杂度优化至 O(n\log n)。

这里额外补充一下卡特兰数，即 C_i。它的通项公式为

C_i=\binom {2n}n-\binom {2n}{n-1}

我们考虑一个模型：从 (0,0) 出发，沿着格路向右向上走到 (n,n)，在任意时刻 y 坐标始终不大于 x 坐标，求所有的方案数。总方案数即为 C_n。其中，y 坐标始终不大于 x 坐标的限制，相当于路径始终不能穿过与 x=y 这条直线。

其中蓝线为分界线，绿线即为一条合法路径。若不考虑限制，那么总方案数相当于在一共 2n 步中，选出 n 步向上走，剩余 n 步向右走，方案数即为 \binom{2n}n。

对于图中红色的线即为一条不合法的路径。我们现在令作一条过 (0,n) 斜率为 1 的线（图中天蓝色的线），所有不合法的路径都会与这条斜线接触。我们将不合法路径以天蓝色的线为对称轴作对称图形（图中橙色的线），这样不合法路径的终点变为 (n-1,n+1)，这样不合法路径的总方案数为：一共 2n 步中选择 n-1 步向右走，剩余 n+1 步向上走，即 \binom{2n}{n-1}。合法路径 = 总路径 - 不合法路径，于是就可以得出 C_n=\binom{2n}n-\binom{2n}{n-1}。

它的递推公式为

C_n=[n=0]+\sum_{j=0}^{n-1}C_j\times C_{n-j-1}

我们再考虑一个模型，也是最常用的模型：n 个点无标号二叉树的个数。首先若 n=0 那么空树即为一个答案，否则考虑枚举左子树的大小，用乘法原理和加法原理得出答案。于是就得到了 C 的递推公式。卡特兰数另外的模型还包括：

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5, P = 998244353; 
int fac[maxn << 1], inv[maxn << 1], n;
int qp(int x, int y) {
    int res = 1;
    for (; y; y >>= 1, x = (1ll * x * x) % P)
        if (y & 1) res = (1ll * res * x) % P;
    return res;
}
void init() {
    fac[0] = 1, inv[0] = 1;
    for (int i = 1; i <= (n << 1); i ++)
        fac[i] = (1ll * fac[i - 1] * i) % P, inv[i] = qp(fac[i], P - 2);
}
int C(int x, int y) {
    if (x < y) return 0;
    int p = (1ll * fac[x] * inv[y]) % P;
    return (1ll * p * inv[x - y]) % P;
}
int Cat(int x) { 
    if (x == 0) return 1;
    return ((C(x << 1, x) - C(x << 1, x - 1)) % P + P) % P; 
}
int siz[maxn], son[maxn][2];
void dfs1(int u) { // 求出子树大小
    if (!u) return ;
    dfs1(son[u][0]), dfs1(son[u][1]);
    siz[u] = 1 + siz[son[u][0]] + siz[son[u][1]];
}
int ans = 0;
void dfs2(int u, int k) { // 统计答案，其中 k 为递归中的系数
    if (!u) return ;
    if (siz[son[u][0]] <= siz[son[u][1]] + 1) // 按照子树大小使用公式计算
        for (int i = 0; i < siz[son[u][0]]; i ++)
            ans = (ans + (1ll * ((1ll * k * Cat(i)) % P) * Cat(siz[u] - i - 1)) % P) % P;
    else {
        int tmp = Cat(siz[u]);
        for (int i = 0; i <= siz[son[u][1]]; i ++)
            tmp = ((tmp - (1ll * Cat(i) * Cat(siz[u] - i - 1)) % P) % P + P) % P;
        // cout << tmp << '\n';
        ans = (ans + (1ll * k * tmp) % P) % P;
    }
    // cout << u << ' ' << ans << ' ' << k << '\n';
    dfs2(son[u][0], (1ll * k * Cat(siz[son[u][1]])) % P), dfs2(son[u][1], k);
}
int main() {
    scanf("%d", &n); init();
    for (int i = 1; i <= n; i ++)
        scanf("%d %d", &son[i][0], &son[i][1]);
    int self = 0;
    for (int i = 1; i < n; i ++) // 注意原题要求非空二叉树，所以答案不能统计空树的情况，故从 i=1 开始枚举。
        self = (1ll * self + Cat(i)) % P;
    dfs1(1), dfs2(1, 1); printf("%d", (1ll * self + 1ll * ans) % P);
    return 0;
}