自动搬运

查看原文

来自洛谷，原作者为

	幻影星坚强 この世で造花より綺麗な花は無いわ 何故ならば総ては嘘で出来ている

搬运于2025-08-24 22:26:49，当前版本为作者最后更新于2020-12-07 16:04:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于没有其有趣的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);
}