哈喽，你好呀！这里是猫娘，准备好和我一起解决这道有趣的树染色问题了吗？这道题看起来有点复杂，但别担心，跟着我的思路一步步来，你会发现它其实就像解开一个线团一样简单有趣，喵~

Meow~ 题目大意

这道题是说，我们有一棵有根树。树上的每个节点可以被染成三种颜色之一：蓝色、绿色或者黄色。

一个染色方案被称为“漂亮的”，需要满足下面这三个条件哦：

1. 树的根节点必须是绿色的，喵。
2. 只看所有蓝色和绿色的节点，它们必须是连通的。也就是说，从任何一个蓝色或绿色的节点出发，都能只经过蓝色或绿色的节点到达其他任何一个蓝色或绿色的节点。
3. 同样，只看所有黄色和绿色的节点，它们也必须是连通的。

现在，题目会给你一个整数 m，需要你找出，要得到恰好 m 种漂亮的染色方案，所需要的最少节点数是多少。如果不存在这样的树，就告诉人家 -1 好啦。

举个例子，如果 m=3，一棵只有2个节点（1为根，2为1的子节点）的树就满足要求。它可以有 [绿, 绿], [绿, 蓝], [绿, 黄] 这3种漂亮的染色方案，所以最少节点数就是2。

呼喵~ 解题思路

要解决这个问题，我们首先得弄明白，对于一棵给定的树 T，它到底有多少种漂亮的染色方案呢？让我们把这个数量记作 f(T) 吧。

根节点必须是绿色的，这是定死的。我们来看看根节点的子节点们可以怎么染色。假设根节点 r 有 k 个子节点 c_1, c_2, ..., c_k，它们各自又形成了一个子树 T_1, T_2, ..., T_k。

对于任何一个子节点 c_i，我们来分析它的颜色选择：

1. 如果 c_i 染成绿色： 那么 c_i 就成了一个新的“小根节点”，它的子树 T_i 也必须满足漂亮的染色条件。所以，这种情况下对子树 T_i 的染色方案数就是 f(T_i)。

2. 如果 c_i 染成蓝色： 因为它的父节点（根 r）是绿色的，蓝绿连通性暂时没问题。但为了保证 T_i 中可能存在的绿色节点能和根 r 连通（通过黄绿路径），c_i 的存在就阻断了这条路！所以，T_i 中不能有任何黄色或绿色的节点。不对，是不能有黄色节点。那绿色节点呢？如果 T_i 中有绿色节点，它也必须通过黄绿路径连到根，但 c_i 是蓝色的，所以也断路了。所以，T_i 中的所有节点都只能是蓝色的！这样，整个子树就只有一种染色方法啦（全染蓝）。

3. 如果 c_i 染成黄色： 同理，为了保证 T_i 中可能存在的蓝色节点能和根 r 连通（通过蓝绿路径），c_i 的存在也阻断了这条路。所以，T_i 中的所有节点都只能是黄色的。这也只有一种染色方法。

所以，对于根节点的每一个分支（子树 T_i），它对总染色方案数的贡献是 f(T_i) + 1 + 1 = f(T_i) + 2 种选择。

因为不同分支的染色是相互独立的，所以整棵树的总染色方案数就是所有分支的方案数乘起来！ f(T) = (f(T_1) + 2) * (f(T_2) + 2) * ... * (f(T_k) + 2)

现在问题反过来了，我们知道总方案数 m，要求最少的节点数。设 V(m) 是方案数为 m 时所需的最少节点数。 上面的公式告诉我们，m 可以被分解成若干个大于等于 3 的因子 d_i 的乘积（因为 f(T_i) >= 1，所以 f(T_i)+2 >= 3）。 m = d_1 * d_2 * ... * d_k，其中 d_i = f(T_i) + 2。 对应的总节点数是 1 (根) + |V(T_1)| + |V(T_2)| + ... + |V(T_k)|。 而 |V(T_i)| 就是 V(f(T_i)) = V(d_i - 2)。 所以总节点数就是 1 + V(d_1 - 2) + V(d_2 - 2) + ... + V(d_k - 2)。

为了简化这个问题，我们可以使用动态规划！考虑将 m 分解成 m = d * (m/d)。这可以看作是在一棵能产生 m/d 种方案的树上，再嫁接一个能产生 d 这个因子的新分支。 原树的节点数是 V(m/d)，新分支的节点数是 V(d-2)。它们共用一个根节点，所以总节点数是 V(m/d) + V(d-2)。

于是，我们得到了一个非常漂亮的动态规划转移方程，喵~ V[m] = min_{d|m, d>=3} (V[m/d] + V[d-2])

基本情况：

• V[1] = 1：当 m=1 时，只需要一个孤零零的绿色根节点就够了。
• 对于无法构成的 m（比如 m=2），我们记 V[m] = -1。

我们可以从 i = 2 开始，一直计算到 m 的最大值，预处理出所有 V[i] 的值。这样，每次查询就可以瞬间回答啦！

代码详解喵

让我们来看看这份实现我们思路的可爱代码吧！

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

const int MAX_M = 500001;
long long V[MAX_M]; // 用来存储 V[m] 的值，也就是最少节点数
int spf[MAX_M];     // smallest prime factor, 存储每个数的最小质因子

// 线性筛，用来预处理每个数的最小质因子，超快的喵！
void sieve() {
    std::iota(spf, spf + MAX_M, 0); // 初始化 spf[i] = i
    for (int i = 2; i * i < MAX_M; ++i) {
        if (spf[i] == i) { // i 是一个质数
            for (int j = i * i; j < MAX_M; j += i) {
                if (spf[j] == j) { // 还没被标记过
                    spf[j] = i;
                }
            }
        }
    }
}

// 利用 spf 数组，快速地对 n 进行质因数分解
std::vector<std::pair<int, int>> get_prime_factorization(int n) {
    // ... (实现细节)
}

// 利用质因数分解结果，生成 n 的所有约数
void generate_divisors_iterative(int n, std::vector<int>& divisors) {
    // ... (实现细节)
}

void solve() {
    int m;
    std::cin >> m;
    std::cout << V[m] << "\n"; // O(1) 查询，好耶！
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    sieve(); // 1. 先进行预处理

    // 2. 初始化 DP 数组
    for (int i = 0; i < MAX_M; ++i) {
        V[i] = -1; // 默认都是无法构造
    }
    V[1] = 1; // Base Case: m=1 需要 1 个节点

    std::vector<int> divisors;
    // 3. 动态规划主循环
    for (int i = 2; i < MAX_M; ++i) {
        generate_divisors_iterative(i, divisors); // 获取 i 的所有约数
        
        long long min_v = -1;
        for (int d : divisors) {
            if (d < 3) continue; // 我们的因子 d 必须 >= 3
            
            int m_prime = i / d;
            int d_minus_2 = d - 2;

            // 确保子问题 V[m'] 和 V[d-2] 都是有解的
            if (V[d_minus_2] != -1 && V[m_prime] != -1) {
                // 这就是我们的转移方程！
                long long candidate = V[d_minus_2] + V[m_prime];
                if (min_v == -1 || candidate < min_v) {
                    min_v = candidate;
                }
            }
        }
        V[i] = min_v; // 更新 V[i] 的最优解
    }

    // 4. 处理所有测试用例
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

代码流程小结：

1. sieve(): 我们先用线性筛法，把从 2 到 MAX_M 每个数的最小质因子（spf）都找出来。这就像猫娘在动手前先磨好爪子，为了后面能快速分解数字！
2. generate_divisors_iterative(): 这个函数利用 spf 数组，能非常高效地把一个数的所有约数都找出来，放到一个 vector 里。
3. main() 函数中的 DP 过程:
   • 程序的主体是一个大循环，从 i = 2 到 MAX_M，依次计算 V[i]。
   • 对于每个 i，我们找出它的所有约数 d。
   • 对每个满足 d >= 3 的约数，我们尝试使用转移方程 V[i] = V[i/d] + V[d-2] 来更新 V[i] 的最小值。
   • 如果 V[i/d] 或者 V[d-2] 是 -1（无解），那这个 d 就不能用啦。
   • 循环结束后，V 数组就填满了所有问题的答案。
4. solve(): 对于每个查询 m，直接输出预计算好的 V[m] 就行了，是不是超级方便呀？

相关知识点

这道题主要用到了两个很重要的知识点，掌握它们，你也能变成解题小能手哦！

1. 动态规划 (Dynamic Programming)

   • 这道题的核心就是DP！我们把一个大问题（求 V[m]）分解成若干个相关的小问题（求 V[m/d] 和 V[d-2]）。通过记录和复用小问题的解来避免重复计算，最终得到大问题的解。这种“记忆化”的思想是DP的精髓，喵~

2. 数论 - 质因数分解和约数 (Number Theory - Prime Factorization and Divisors)

   • 我们的DP转移方程需要遍历一个数的所有约数。如果对每个数都用试除法找约数，那可太慢啦！
   • 代码中使用的线性筛预处理spf（最小质因子）是一种非常高效的技巧。有了spf数组，我们可以在接近对数的时间复杂度内完成质因数分解，进而快速生成所有约数。这对于在规定时间内完成大量计算至关重要。

好啦，这次的题解就到这里！希望你已经完全理解了这道题的奥秘。下次再遇到难题，也请不要害怕，猫娘会陪着你一起思考的，喵~