自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

搬运于2025-08-24 22:11:53，当前版本为作者最后更新于2019-09-11 19:25:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题改自 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$ 个孩子的树，通过枚举置换群：

读者可自己尝试推导 $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)$，常数显而易见的大，欢迎有兴趣的同学来实现。