题目大意

有一棵有根树，每个节点可以染成蓝色（$b$）、绿色（$g$）、黄色（$y$）。
一种染色称为美丽的，如果：

1. 根节点是绿色；
2. 所有蓝色和绿色节点构成的点集是连通的（路径上不能出现黄色节点）；
3. 所有黄色和绿色节点构成的点集是连通的（路径上不能出现蓝色节点）。

给定 $m$，求顶点数最少的有根树，使得它恰好有 $m$ 种美丽染色方案。如果不存在这样的树，输出 $-1$。

---

核心观察

关键性质：如果一个节点不是绿色，那么它的整个子树必须染成同一种颜色（全蓝或全黄）。

证明：
假设一个蓝色节点 $v$ 有一个黄色后代 $u$。从 $u$ 到根的路径必须经过 $v$，但 $v$ 是蓝色，而黄+绿连通性要求路径上不能有蓝色节点，矛盾。同理，蓝色节点不能有绿色后代（因为绿色到根经过蓝色会破坏黄+绿连通性）。所以蓝色节点的子树必须全蓝。对称地，黄色节点的子树必须全黄。
绿色节点无此限制。

---

正向计数（已知树，求美丽染色数）

设 $cnt_v$ 表示：在以 $v$ 为根的子树中，$v$ 固定为绿色时的美丽染色方案数。

• 若 $v$ 是叶子（无子节点）：$cnt_v = 1$。
• 若 $v$ 有子节点 $u_1, u_2, \dots, u_k$：
  • 每个子节点 $u_i$ 可以染成绿、蓝、黄。
  • 若染成绿色：有 $cnt_{u_i}$ 种方式。
  • 若染成蓝色或黄色：整个 $u_i$ 子树必须同色，只有 $1$ 种方式。
  • 因此，$u_i$ 的染色方式数为 $cnt_{u_i} + 2$。
  • 各子节点独立，所以：$$cnt_v = \prod_{i=1}^k (cnt_{u_i} + 2)$$

整棵树的美丽染色数就是 $cnt_{\text{root}}$（因为根固定为绿色）。

---

逆向问题（给定 $m$，求最少顶点数）

我们要求：构造一棵树，使 $cnt_{\text{root}} = m$，且顶点数最小。

---

状态定义（标程中的偏移）

标程中：

• $dp[x]$：当 $cnt_{\text{root}} = x-2$ 时的最少顶点数。
• $dp2[x]$：当 $cnt_{\text{root}} = x-2$ 且根至少有 2 个子节点时的最少顶点数。

并且输入 $m$ 时调用 $calc(m+2)$，输出结果即为顶点数。
验证：

• $m=1$ → $calc(3)=1$，输出 $1$（顶点数 $1$）
• $m=3$ → $calc(5)=2$，输出 $2$
• $m=5$ → $calc(7)=3$，输出 $3$
• $m=7$ → $calc(9)=4$，输出 $4$
• $m=9$ → $calc(11)=3$，输出 $3$

因此 $calc(x)$ 返回的就是顶点数，且 $x = m+2$。
所以 $dp[3]=1$ 对应 $cnt_{\text{root}}=1$ 时顶点数 $1$（只有根），$dp[1]=0$ 是边界占位。

---

递推关系

情况 1：根只有一个子节点（链状）

此时子节点必须为绿色（否则 $cnt_{\text{root}}=3$ 固定）。
设子节点的 $cnt = y$，则：

$$x-2 = y + 2 \quad\Rightarrow\quad y = x-4$$

顶点数 $= 1 + dp[x-2]$（因为 $dp[x-2]$ 对应 $cnt_{\text{root}} = x-4$ 时的顶点数）。
标程中体现为：

$$dp[x] = dp2[x-2] + 1$$

这里 $dp2$ 用于多子节点情况，但链情况实际只用 $dp$ 自身，而 $dp2$ 的初始值设为 $dp[x]$ 保证了取 min 时正确。

情况 2：根有多个子节点（至少 2 个）

设子节点的 $cnt$ 分别为 $c_1, \dots, c_k$（$k\ge 2$），则：

$$m = \prod_{i=1}^k (c_i + 2)$$

记 $a_i = c_i + 2 \ge 3$，则 $m = \prod a_i$，$k \ge 2$。
顶点数 $= 1 + \sum_{i=1}^k dp[a_i]$（因为 $dp[a_i]$ 对应 $cnt = a_i-2 = c_i$ 时的顶点数）。

于是定义：

$$dp2[m] = \min_{\substack{m = \prod a_i \\ a_i \ge 3,\ k\ge 2}} \left(1 + \sum_{i=1}^k dp[a_i]\right) $$

---

计算 $dp2$

对于 $m$ 的一个因子 $d \ge 3$，我们可以拆出一个 $a_i = d$，剩余部分为 $m/d$。
剩余部分可以继续分解为多个因子（可能不止一个），因此用 $dp2$ 递归：

$$dp2[m] = \min_{d \mid m,\ d \ge 3} \big( dp[d] + dp2[m/d] \big) $$

同时，$dp2[m]$ 也可取 $dp[m]$ 作为初始值（但 $dp[m]$ 可能对应一个子节点，不满足 $k\ge 2$，不过取 min 后会被更优的多子节点方案替代）。

标程中的实现：

dp2[x] = calc(x);
for(auto y : divisors[x]) 
    dp2[x] = min(dp2[x], calc(y) + calc2(x / y));

即：

$$dp2[x] = \min\left(dp[x],\ \min_{d \mid x,\ d \ge 3} \big( dp[d] + dp2[x/d] \big) \right) $$

---

综合递推

对于 $x \ge 5$ 且 $x$ 为奇数：

$$dp[x] = \min(1 + dp[x-2],\ dp2[x])$$

边界：

• $dp[1] = 0$
• $dp[3] = 1$

最后，输入 $m$ 时：

• 若 $m$ 为偶数 → 输出 $-1$
• 否则输出 $dp[m+2]$

---

为什么 $m$ 必为奇数？

• 叶子节点：$cnt = 1$（奇数）
• 内部节点：$cnt = \prod (cnt_u + 2)$，$cnt_u$ 是奇数 → $cnt_u+2$ 是奇数 → 奇数乘积仍为奇数。
• 所以 $cnt_{\text{root}}$ 总是奇数，$m$ 为偶数时无解。

---

算法步骤

1. 预处理因子（$N = 500043$）：

   for i = 2 to N-1:
       for j = 2*i, 3*i, ... < N:
           divisors[j].push_back(i)
   

   复杂度 $O(N \log N)$。

2. 动态规划（只计算奇数 $x$）：

   • 初始化 $dp[1]=0,\ dp[3]=1$，$dp$ 和 $dp2$ 数组其余为 $-1$。
   • 对每个奇数 $x$ 从 $5$ 到 $N-1$：
     • 计算 $dp2[x]$ 使用因子列表。
     • 计算 $dp[x] = \min(1+dp[x-2],\ dp2[x])$。

3. 回答查询：

   • 读入 $m$，若 $m$ 为偶数，输出 $-1$。
   • 否则输出 $dp[m+2]$。

---

示例验证

$m$	$m+2$	$dp[m+2]$	输出
1	3	1
3	5	2
5	7	3
7	9	4
9	11	3

与题目样例完全一致。

---

复杂度分析

• 预处理因子：$O(N \log N)$
• DP 每个状态遍历其所有因子：总 $O(N \log N)$（调和级数）
• 每个查询 $O(1)$

对于 $N = 5\times 10^5$，完全可行。

---

总结

本题的核心在于：

1. 发现非绿色节点的子树必须单色。
2. 推导出 $cnt$ 的乘积递推式。
3. 将问题转化为对 $m$ 的因子分解，并用动态规划求最小顶点数。
4. 利用预处理因子将复杂度优化到 $O(M \log M)$。