题解：AT_abc222_h [ABC222H] Beautiful Binary Tree

· · 题解

Lagrange 反演板题。

考虑题目中什么样的树是合法的。

每次操作可以将一个节点的权值移到其父亲或爷爷上，最多操作 n-1 次，需要使根节点权值为 1，其余节点权值为 0。

每次操作节点权值总和不变，所以原树的 1 的个数为 n。

一共有 n 个 1，除了在根节点的 1 其余每个 1 都需要往根节点挪，且次数最少需要 n-1，这说明根节点肯定为 1。

每次移动只能移动到其父亲或爷爷上，说明树上不可能存在一条从祖先到孙子的路径的点权为 1001，不然操作会多一次。

又因为叶子节点一定为 1，那么肯定不存在两个相邻的点权值均为 0。

接下来，dp 方程就很好列了，设 f_{i,0/1} 表示一共有 i 个 1，根节点的权值为 0/1，且不存在两个相邻点权值均为 0 的方案数。

如果根节点权值为 0，那么其儿子权值一定为 1，转移方程为：

f_{i,0}=2f_{i,1}+\sum_{j=1}^{i-1}f_{j,1}f_{i-j,1}

如果根节点权值为 1，那么其儿子的权值随便取，转移方程为：

f_{i,1}=2(f_{i-1,0}+f_{i-1,1})+\sum_{j=1}^{i-2}(f_{j,0}+f_{j,1})(f_{i-1-j,0}+f_{i-1-j,1})

转移的边界为 f_{1,0}=2,f_{1,1}=1，直接 O(n^2) 转移即可。

发现这个式子特别像卷积，所以我们考虑写出这两个 dp 数组的 OGF，设：

F_0(x)=\sum_{i=1}f_{i,0}x^i \\ F_1(x)=\sum_{i=1}f_{i,1}x^i

那么方程式就变为：

F_0=F_1^2+2F_1 \\ F_1=x(F_0+F_1)^2+2x(F_0+F_1)+x

第二个方程最后 +x 的原因是初始条件 f_{1,1}=1 漏算了。

化简并将，将 F_0 带入，得：

\begin{aligned} F_1&=x(F_0+F_1+1)^2 \\ &=x(F_1^2+3F_1+1)^2 \\ x&=\frac{F_1}{(F_1^2+3F_1+1)^2} \end{aligned}

由于 [x^0]F_1(x)=0，所以 F_0(x) 有复合逆，设 G(x)=\frac{x}{(x^2+3x+1)^2}，那么 G(x) 就是 F_0(x) 的复合逆。

套用 Lagrange 反演公式：

\begin{aligned} [x^n]F_1(x)&=\frac 1n[x^{n-1}]\left(\frac{x}{G(x)}\right)^n \\ &=\frac 1n[x^{n-1}](x^2+3x+1)^{2n} \end{aligned}

一种方法是线性预处理组合数，直接用三项式定理 O(n) 计算。

还有另一种常数更小的方法是设 H(x)=(x^2+3x+1)^{2n}，那么：

\begin{aligned} H'(x)&=2n(x^2+3x+1)^{2n-1}(2x+3) \\ &=\frac{H(x)}{x^2+3x+1}2n(2x+3) \\ (x^2+3x+1)H'(x)&=2n(2x+3)H(x) \\ H'(x)&=-3xH'(x)+6nH(x)-x^2H'(x)+4nxH(x) \end{aligned}

对比 x^{i-1} 系数，得：

\begin{aligned} ih_i&=-3(i-1)h_{i-1}+6nh_{i-1}-(i-2)h_{i-2}+4nh_{i-2} \\ &=(6n-3i+3)h_{i-1}+(4n-i+2)h_{i-2} \end{aligned}

边界条件是 h_0=1,h_1=6n，O(n) 递推计算，最后答案为 \frac 1nh_{n-1}。

还可以优化，得到这个式子后，可以运用 P6115 【模板】整式递推，将复杂度优化到 O(\sqrt n\log n)。（但是我不会）