CF2112E Tree Colorings

原题链接：E. Tree Colorings

Tag：数学、DP

题目描述

给定一棵有根的无向树。每个顶点都可以染成蓝色、绿色或黄色。如果一种着色方案满足一下条件，那么这种着色就被称为做美丽着色：

根是绿色的
如果考虑所有的蓝色和绿色点，它们之间可以相互到达，且不经过任何黄色点；
如果考虑所有的黄色和绿色顶，它们之间可以相互到达，且不经过任何蓝色点；

给你一个整数 \(m\) 。任务是计算一棵树中最少有多少个顶点，而这棵树上有确切的 \(m\) 种美丽的着色方案。

数据说明：

\(1 \le t \le 10^5\)
\(1 \le m \le 5 \cdot 10^5\)

分析

首先可以观察到，对于任意一种树的构造，其美丽着色方案一定是一个奇数。

证明

我们考虑一个所有的点都染色成绿色的树，这是一种方案。剩下的方案是在这个树的基础把其某个子树染成同一种颜色，每多染一个叶子，贡献都是二。

因此偶数一定是无法构造的。

现在我们已经知道了方案数无法为偶数，我们思考一下这个东西是如何转移的。

我们加一个叶子上去，这个叶子颜色有三种可能，其父亲也有三种可能。那么合法的有哪几种情况呢？仔细思考可以发现，我们加一个点进去，要么我们加的是绿色的，这个点就和根连通且同色。要么就是我们加了一个蓝或绿，其和已有的蓝绿色保持连通。所以实际上是多了两个方案。

因此假设某个树，其现在有 \(x-2\) 种方案，那么我们挂一个叶子上去，方案数就变成 \((x-2)+2=x\)，并且节点数量多了一。

所以这里的转移是：

\[\begin{equation} dp[x] = dp[x-2] + 1 \end{equation}\]

接着思考可以发现，我们其实还有一类合并树的方法。

假设我们当前有两颗子树 \(T_1\) 和 \(T_2\) 我们现在要把这两棵树连到同一个根上：

新的根肯定是绿色的
子树内部的结构一定不被破坏

那么合并其实就是一个乘法原理，方案数是 \(x \times \frac{m}{x} = m\)，节点数是 \(dp[x] + dp[m/x]\)。那么很显然我们在转移的时候要对于一个 \(m\) 来枚举其所有的因子 \(m = x \cdot (m/x)\)，取最小值。

\[\begin{equation} dp[m] = \min_{1<x<m,x \mid m}(dp[x]+dp[m/x]) \end{equation}\]

考虑一下如何实现上述的做法，暴力分解显然是不可取的，所以我们使用线性筛预处理出每个数字的最小值因子。之后对于每一个奇数，我们先对其进行质因子分解，对于其所有因子进行合并的转移。

于是我们就有了先 \(O(N\log \log N)\) 处理最小值因子，之后通过 \(O(N\log N)\) 的 \(\text{DP}\) 处理，每次查询只需要 \(O(1)\) 的时间处理。故总复杂度为 \(O(N\log N + T)\)

代码实现

const int N = 5e5 + 5;

void NeverSayNever() {
    vector<int> sie(N + 1);
    for (int i = 2; i <= N; i++) {
        if (sie[i] == 0) {
            for (int j = i; j <= N; j += i) {
                if (sie[j] == 0) {
                    sie[j] = i;
                }
            }
        }
    }
    int inf = INT_MAX;
    vector<int> dp(N + 1, inf);
    dp[1] = 0;
    vector<PII> pf;
    vector<int> div;
    for (int m = 3; m <= N; m += 2) {
        int &ans = dp[m];
        ans = dp[m - 2] + 1;
        pf.clear();
        int t = m;
        while (t > 1) {
            int p = sie[t], cnt = 0;
            while (t % p == 0) {
                t /= p;
                cnt++;
            }
            pf.push_back({p, cnt});
        }
        div.clear();
        div.push_back(1);
        for (auto &[p, cnt] : pf) {
            int sz = div.size();
            int tmp = 1;
            for (int i = 1; i <= cnt; i++) {
                tmp *= p;
                for (int j = 0; j < sz; j++)
                    div.push_back(div[j] * tmp);
            }
        }
        for (auto &x : div)
            if (x > 1 && x < m && dp[x] < inf && dp[m / x] < inf)
                ans = min(ans, dp[x] + dp[m / x]);
        dp[m] = ans;
    }
    int T;
    cin >> T;
    while (T--) {
        int x; cin >> x;
        if (x % 2 == 0) cout << -1 << endl;
        else cout << dp[x] + 1 << endl;
    }
}

日志

本页面创建于 2025/6/24 1:49