题解 P5547 【[BJ United Round #3] 三色树】

· · 题解

这道题改自 ProjectEuler#677。

思路要点

首先考虑无标号有根树，我们只需维护 dp 数组 R(n), B(n), Y(n) 即可。通过更新 dp 数组 Q(d, n) 表示此时不在意节点的根的颜色，且根的度数为 d 即可维护红根和蓝根，W(d, n) 用于维护孩子没有黄根树的，这可以帮助计算黄根。每次 update 会消耗 \Theta(n) 的时间，比如说已经计算完了 R(n) 的值，那么它作为子树有可能出现了 k 次，则选出 \displaystyle \binom{R(n) + k - 1}{k - 1} 种方案，令 Q(d,N) 加上 \binom{R(n) + k - 1}{k - 1} Q(d - k, N - kn)。

这一部分的复杂度为 \Theta(n^2)。

计算无标号无根树的要点是观察树的一个特殊点：一颗树要么存在唯一一个重心使得任何一个子树的大小均 < \frac{n}2，要么存在一个“重边”使得它将树恰好分为大小为 \frac n2 的两部分。

对于前者部分的计数，我们只需将 dp 数组计算到 \lceil \frac n2 \rceil - 1 时，将 Q,R 数组取出。对于后者，若 n 是偶数，当计算完 \frac n2 的 dp 值时，将 R, B, Y 用于计算即可。

如何做到更快

考虑计算 R,B,Y 的生成函数 G_R(x), G_B(x), G_Y(x)。

我们记 S = G_R + G_B + G_Y，我们使用 Pólya 计数定理表示 3 个孩子的树，通过枚举置换群：

\frac{S(x)^3 + 3S(x^2)S(x) + 2S(x^3)}{3!}

读者可自己尝试推导 4 和 2 个孩子的树。

由此我们可以通过 G_R, G_B, G_Y 自身带入 x, x^2, x^3 这些的多项式来表示。接下来考虑如何求解。

我们让 G_R, G_B, G_Y 放在一起进行迭代，我们考虑倍增，由于已经计算出了前 \frac n2 项，所有带入 x^2, x^3 的部分就已经确定了，我们可以认为是常数。接下来就是一个关于 G_R, G_B, G_Y 的三元三次方程，这依然可以通过牛顿迭代解决，也就是这等价于根据 G_R, G_B, G_Y 的定义式得到了 3 个它们之间的关系式 E_R/E_B/E_Y(G_R, G_B, G_Y) = 0，将 E_R/E_B/E_Y(u, v, w) 在 G_R, G_B, G_Y 处泰勒展开就是一次方程，求解一个三元一次方程即可。

本算法的复杂度为 \Theta(n\log n)，常数显而易见的大，欢迎有兴趣的同学来实现。