E. Tree Colorings

问题描述

考虑一棵有根无向树。每个顶点可以被染成蓝色、绿色或黄色。一个染色方案被称为美丽的，如果它满足以下条件：

• 树的根是绿色的
• 如果只考虑所有蓝色和绿色的顶点，它们之间可以相互到达，而无需经过任何黄色顶点
• 如果只考虑所有黄色和绿色的顶点，它们之间可以相互到达，而无需经过任何蓝色顶点

给定一个整数 $m$。你的任务是计算一个恰好有 $m$ 种美丽染色方案的树所需的最小顶点数。

输入

第一行包含一个整数 $t$ $(1 \leq t \leq 10^5)$ — 测试用例的数量。

每个测试用例的唯一一行包含一个整数 $m$ $(1 \leq m \leq 5 \cdot 10^5)$。

输出

对于每个测试用例，打印一个整数 — 恰好有 $m$ 种美丽染色方案的树的最小顶点数。如果不存在这样的树，则打印 $-1$。

题解 (来自官方题解)

关键观察

重要提示：如果一个顶点不是绿色的，它的整个子树必须被染成相同的颜色。例如，如果一个顶点是蓝色的，并且它有一个绿色或黄色的后代，那么如果不经过那个蓝色的顶点，根节点就无法到达那个后代。同时，绿色的顶点不施加任何额外的约束。

计算美丽的染色方案数

利用这个观察，让我们探讨如何使用动态规划来解决原问题的逆问题（即，给定一棵树，计算美丽染色方案的数量）。

设 $cnt_v$ 是在顶点 $v$ 本身为绿色的前提下，为以 $v$ 为根的子树进行染色的方法数。由于 $v$ 是绿色的，它的每个子顶点可以被染成任何颜色：

• 如果一个子节点 $u$ 是绿色的，有 $cnt_u$ 种方法来为其子树染色
• 如果 $u$ 是蓝色或黄色的，只有一种方法来为其子树染色

因此，对于 $u$ 的总染色方案数是 $cnt_u + 2$。

由于每个子树可以独立染色：

其中 $u_1, u_2, \ldots, u_k$ 是 $v$ 的子节点。

动态规划方法

注意到上面的公式显示，一棵树的染色方案数仅取决于其子树的染色方案数。因此，我们可以使用以下动态规划方法来解决原问题：

设 $dp_m$ 是恰好有 $m$ 种美丽染色方案的树的最小顶点数。

为了计算这个值，我们可以利用一棵树的染色方案数是其子树染色方案数的乘积这一事实。让我们遍历最后一个子树的染色方案数（记为 $x$），那么：

对于所有的 $x$ 值。注意 $x$ 必须是 $m$ 的一个因子。

优化

为了加速解法，我们可以遍历 $x$ 直到 $\sqrt{m}$ 或者 $m/x$ 直到 $\sqrt{m}$。

时间复杂度分析

这种方法产生了一个时间复杂度为 $O(M\sqrt{M})$ 的解法，其中 $M$ 是我们需要考虑的最大染色方案数。这足以通过，但我们可以将其加速到 $O(M \log M)$，如下所示：

对于从 $1$ 到 $M$ 的每个整数 $x$，我们准备它的因子列表。我们可以遍历因子 $d$ 并将其附加到整数 $2d, 3d, 4d, \ldots$ 的因子列表中。

整数 $d$ 将在 $O(M/d)$ 的时间内被处理，所以总共我们达到了一个复杂度：

因为它是一个调和级数（乘以 $M$）。

提交链接