[题解] [Mivik 的萌新赛 & Chino 的比赛 2020] Galgame

定义两棵二叉树的大小关系：

• 若它们皆为空，则相等；
• 若它们的大小不同，则大小更小的更小；
• 若它们的左子树不同，则左子树小的更小；
• 否则其大小关系等价于它们右子树的大小关系。

给你一棵二叉树，问有多少二叉树比它小。

$1\le n\le 10^6$

原题链接

---

思路

Subtask 1

暴力枚举也许能过。

Subtask 2

记 $f(x)$ 为和 x 这一二叉树结点数相同但更为无趣二叉树数目，则有：

$$
f(x)=f(lson(x))C_{size(rson(x))}+f(rson(x))+\sum_{i=0}^{size(lson(x))-1}C_i C_{size(x)-i-1}
$$

其中 $C_n$ 为卡特兰数。然后我们 $O(n^2)$ 计算即可。

满分做法

我们对上面的做法做一个优化：我们先预处理出卡特兰数列的自卷积，然后对于 $size(lson(x))\le size(rson(x))$ 的情况，我们和上面一样暴力算；然后对于 $size(lson(x))>size(rson(x))$ 的情况，我们从预处理出的卷积里面减去多算的部分。然后，注意到卡特兰数列的自卷积等于它本身（偏移了一位），因此我们连卷积都不需要计算了。具体的，设卡特兰数列的生成函数是 $H(x)$，我们有 $H(x)^2\cdot x+1=H(x)$，我们所需要的卡特兰数自卷积 $F(x)=H(x)^2$，那么有 $[x^i]F(x)=[x^i]\left(\frac{H(x)-1}{x}\right)=[x^{i+1}]H(x)$。

这样实际上是对的。我们对每一个点考虑它会对时间复杂度产生多大贡献：自下而上地，如果一个点贡献所在的子树的 $size$ 是我们决定计算的部分，那么整棵树的大小必定大于等于这个点所在子树大小的两倍，也就是说，一个点如果想对时间复杂度产生 $1$ 的贡献，则其所在子树大小至少会增大 2 倍。因此一个点最多对时间复杂度产生 $\log n$ 的贡献，则总时间复杂度最劣为 $O(n\log n)$。

代码

mivik.h

代码