CF2112E Tree Colorings 题解

lucasincyber · 2025-11-21 17:41:39 · 题解

题目传送门

思路

首先考虑一个类似的问题如何解决：给定一棵树，求这棵树美丽的染色方案数。这个问题可以用一个树形 DP 解决。

首先，有一个性质。整棵树被分成了几个同颜色的连通块：包含根节点的绿色连通块，其余的子树要么全染黄，要么全染蓝。这样才可以满足这几个条件。所以设 dp_u 代表以 u 为根的子树中美丽染色的方案数。那就从 v \in son_u 向 u 转移。每一次有 3 种情况：保留以 v 为根的子树不变、全染黄、或全染蓝。所以：

其中叶子节点的 dp_u = 1。我们发现所有 dp_u 一定为奇数（因为 +2 不改变奇偶性），所以当且仅当 u \equiv 1 \pmod 2，才会有答案，否则输出 -1。

回到原问题，设 f_i 代表美丽染色方案数恰好为 i 的有根树节点的最小值。那我们可以考虑将两棵子树合并。由上面的问题可知如果第一棵子树的方案数为 i，第二棵子树的方案数为 j，则这棵树就有 (i + 2)(j + 2) 种方案数。那我们直接枚举其中一棵子树转移即可：

其中 j 代表其他的方案，\displaystyle \frac{i}{j} 为枚举的那棵子树的大小。因为需要 1 \sim m 的所有因数，可以用

for (int i = 1; i <= m; i++)
        for (int j = i; j <= m; j += i)
            fact[j].push_back(i);

求出 1 \sim m 的每一个数的所有因数。时间复杂度 \sum \limits_{i=1}^n \displaystyle \frac {n}{i} \approx \mathcal{O}(n \log n)。

预处理 f，最终时间复杂度为 \mathcal{O}(n \log n + t)。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int t, m;
int f[N];
vector<int> fact[N];

int main()
{
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i < N; i += 2)
        for (int j = i; j < N; j += i)
            fact[j].push_back(i);
    f[0] = 0, f[1] = 1;
    for (int i = 3; i < N; i += 2)
        for (int j : fact[i])
            f[i] = min(f[i], f[j] + f[(i / j) - 2]);
    scanf("%d", &t);
    while (t--)
    {
        int m;
        scanf("%d", &m);
        if (f[m] <= 1e9) printf("%d\n", f[m]);
        else printf("-1\n");
    }
    return 0;
}