题解 P7118 【Galgame】

· · 题解

对于没有其有趣的gal我们可以分成两类——节点个数不同的与节点个数相同的。

对于节点个数小于原树的二叉树，形态显然没有要求，所以就是卡特兰数。于是我们能 O(n) 求出所有节点个数不同的，没其有趣的gal。

对于节点个数相同的，那么考虑另外两个约束条件，他会先走 A 再走 B ，递归比较两个树的子树大小。在一棵不平衡的子树内，设原树 A 边下的子树大小为 S ，总子树大小为 n，那么没其有趣的gal数量就是 \sum\limits_{i=0}^{S-1}f_i\times f_{n-i-1} ，其中 f 代表卡特兰数。而如果前面走 A 边的话剩下 B 边的子树就可以随便放，再乘算上贡献即可。

long long ksm(long long x, long long y)
{
    long long m = 1;
    for (; y > 0; y >>= 1)
    {
        if(y & 1)
        m = m * x % MOD;
        x = x * x % MOD;
    }
    return m;
}
long long C(long long x, long long y)
{
    return jc[x] * jcny[y] % MOD * jcny[x - y] % MOD;
}
long long siz[N];
void dfs(int o)
{
    siz[o] = 1;
    if(a[o])
    dfs(a[o]);
    if(b[o])
    dfs(b[o]);
    siz[o] += siz[a[o]] + siz[b[o]];
}
long long ans;
void dfs1(int o, long long mul)
{
    for (int i = 0; i < siz[a[o]]; ++ i)
    {
        (ans += mul * ktl[i] % MOD * ktl[siz[o] - 1 - i] % MOD) %= MOD;
    }//假如在这个节点左右两棵子树不平衡了就算上贡献
    //否则是平衡的，递归处理两个儿子
    if(a[o])
    dfs1(a[o], mul * ktl[siz[b[o]]] % MOD);//如果走A那么就不用考虑B在此刻是否平衡，反正肯定是不平衡的，所以B就可以随便放了
    if(b[o])
    dfs1(b[o], mul);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%d%d", &a[i], &b[i]);
    }
    jc[0] = jcny[0] = 1;
    for (int i = 1; i <= 2 * n; ++ i)
    {
        jc[i] = jc[i - 1] * i % MOD;
        jcny[i] = ksm(jc[i], MOD - 2);
    }
    ktl[0] = 1;
    for (int i = 1; i <= n; ++ i)
    {
        ktl[i] = (C(2 * i, i) - C(2 * i, i - 1) + MOD) % MOD;
    }//计算卡特兰数
    for (int i = 1; i < n; ++ i)
    {
        (ans += ktl[i]) %= MOD;
    }//算个数小于原gal的gal个数
    dfs(1);
    dfs1(1, 1);
    printf("%lld", ans);
}

幸运的是，这样做是 O(n^2)的。

@8fb8721ffd890897190482c717cea26c（已加密） 神仙提出了启发式合并的思想，我们计算贡献的式子是 \sum\limits_{i=0}^{S-1}f_i\times f_{n-i-1}，它是和A的子树的大小有关的，假如B的子树大小比A小通过B转移肯定更优，而事实上没其有趣的gal数量相当于总方案数减至少和其一样有趣的gal数量，那么就可以用 f_n -\sum\limits_{i=S}^nf_i\times f_{n-i-1} 得到该子树的答案，时间复杂度和大部分启发式合并一样为 O(nlogn)


void dfs1(int o, long long mul)
{
    if(siz[a[o]] <= siz[b[o]] + 1)
    for (int i = 0; i < siz[a[o]]; ++ i)
    {
        (ans += mul * ktl[i] % MOD * ktl[siz[o] - 1 - i] % MOD) %= MOD;
    }
    else
    {
        ans += ktl[siz[o]] * mul;
        for (int i = 0; i <= siz[b[o]]; ++ i)
        {
            (ans += mul * (-(ktl[i] % MOD * ktl[siz[o] - 1 - i] % MOD) + MOD) % MOD) %= MOD;
        }
    }
    if(a[o])
    dfs1(a[o], mul * ktl[siz[b[o]]] % MOD);
    if(b[o])
    dfs1(b[o], mul);
}