D. 13th Labour of Heracles - 题解

比赛与标签

比赛: Good Bye 2020 标签: data structures, greedy, sortings, trees 难度: *1500

题目大意喵~

主人，你好呀！这道题是赫拉克勒斯的第十三项试炼，听起来就好厉害的样子呢，我们一起来挑战吧！(๑•̀ㅂ•́)و✧

题目给了我们一棵有 n 个节点的树，每个节点都有一个自己的重量 w_i。我们需要对这棵树的 n-1 条边进行 k-染色。k 的取值范围是从 1 到 n-1。

k-染色：就是给每条边分配 k 种颜色中的一种。
颜色子图：对于某一种颜色，所有染上这种颜色的边和它们所连接的节点，共同构成了一个“颜色子图”。
子图的价值：一个颜色子图可能会分成好几个连通块，它的价值就等于其中节点重量和最大的那个连通块的价值。
k-染色的总价值：把 k 种颜色的子图价值全部加起来，就是这次 k-染色的总价值。

我们的任务是，对于每一个 k（从 1 到 n-1），找出一种最优的染色方案，使得 k-染色的总价值最大，然后依次输出这些最大值。

简单来说，就是对 k=1, 2, ..., n-1，分别求出最大的染色总价值~

解题思路大揭秘！

这道题看起来有点复杂，又是染色又是子图的，但别怕，让本喵带你一步步把它分解开来！ฅ'ω'ฅ

基础情况：k=1

我们先从最简单的情况开始想，当 k=1 的时候会发生什么呢？这时，所有 n-1 条边都只能染上同一种颜色。那么，这个颜色的子图就是整棵树本身！因为树是连通的，所以只有一个连通块，它的价值就是所有节点的重量总和。所以，对于 k=1，最大总价值就是 sum(w_i)。这是我们计算后续价值的基础哦！

核心洞察：价值从哪里来？

现在我们考虑 k > 1 的情况。总价值是怎么计算的呢？是所有颜色子图的价值之和。 总价值 = value(子图_1) + value(子图_2) + ... + value(子图_k)

我们换个角度思考，一个节点的重量 w_i 会被计算几次呢？一个节点 i，只要它连接的边中，至少有一条被染成了颜色 c，那么这个节点 i 就会出现在颜色 c 的子图中，它的重量 w_i 就会对 value(子图_c) 产生贡献。

关键点来啦！如果一个节点 i 连接了多条边，而这些边被染上了不同的颜色，比如颜色 c1, c2, c3... 那么节点 i 就会同时出现在 子图_c1, 子图_c2, 子图_c3... 中。它的重量 w_i 就会被重复计算！

所以，我们的目标就是，通过巧妙地染色，让那些重量大的节点被尽可能多地重复计算，这样总价值就会变大啦！

贪心策略的诞生

一个节点 i 的度是 degree[i]，表示它连接了 degree[i] 条边。

如果我们把这 degree[i] 条边都染成同一种颜色，那么 w_i 只会被计算 1 次。
如果我们把它们染成 2 种不同的颜色，w_i 就会被计算 2 次，我们获得了 w_i 的一次“额外”贡献，也就是一个奖励（Bonus）。
如果我们把它们染成 m 种不同的颜色，w_i 就会被计算 m 次，我们获得了 m-1 次奖励。

一个节点 i 最多能提供 degree[i] - 1 次奖励，每次奖励的价值就是 w_i。这是因为它最多可以把 degree[i] 条边染成 degree[i] 种不同的颜色。

现在问题就清晰了！

k=1 的时候，我们有一个基础价值 sum(w_i)。
当 k 从 1 增加到 2 时，我们多了一种颜色可以用。这意味着我们可以在某个节点上，把原本同色的两条边，染成不同的颜色。为了让总价值增加得最多，我们应该选择哪个节点来做这个“分裂”操作呢？当然是 w_i 最大的那个节点（前提是它的度 degree[i] >= 2）！这样我们就能获得最大的奖励 w_i。
当 k 从 2 增加到 3 时，我们又多了一种颜色。我们可以再次进行一次“分裂”操作。我们应该选择当前所有可用的奖励中，价值最大的那个。

这就形成了一个非常漂亮的贪心策略，喵~

计算出 k=1 时的基础总价值 total_sum = sum(w_i)。
找出所有可能的奖励：对于每个节点 i，它能提供 degree[i] - 1 个价值为 w_i 的奖励。我们把所有这些奖励收集到一个列表里。
将这个奖励列表从大到小排序。
k=2 的总价值 = total_sum + 最大的那个奖励。
k=3 的总价值 = k=2 的总价值 + 第二大的那个奖励。
...以此类推，直到 k=n-1。

总共可以进行 n-2 次“分裂”操作（因为 sum(degree[i] - 1) = sum(degree[i]) - n = 2*(n-1) - n = n-2），正好对应 k 从 2 到 n-1 的 n-2 个值。

是不是一下子就变得很简单了呀？主人只要能看透问题的本质，把复杂的问题转化为简单的贪心选择，就一定能轻松解决的喵！

代码实现时间到！

下面就是把我们的贪心思路变成代码的时刻啦！

cpp

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

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> w(n);
    long long total_weight_sum = 0;
    // 读入每个节点的权重，并计算总权重和
    for (int i = 0; i < n; ++i) {
        std::cin >> w[i];
        total_weight_sum += w[i];
    }

    // 使用一个vector来记录每个节点的度
    std::vector<int> degree(n, 0);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u; --v; // 转换为0-indexed
        degree[u]++;
        degree[v]++;
    }

    // 创建一个列表来存放所有可能的奖励值
    std::vector<long long> bonuses;
    // 预分配空间可以稍微提高效率喵~
    if (n > 2) {
        bonuses.reserve(n - 2);
    }
    for (int i = 0; i < n; ++i) {
        // 每个节点可以提供 degree[i] - 1 次奖励
        for (int j = 0; j < degree[i] - 1; ++j) {
            bonuses.push_back(w[i]);
        }
    }

    // 将所有奖励值从大到小排序，这样我们就可以贪心地选取了
    std::sort(bonuses.begin(), bonuses.end(), std::greater<long long>());

    // current_sum 初始化为 k=1 时的总价值
    long long current_sum = total_weight_sum;
    std::cout << current_sum;

    // 依次计算 k=2, 3, ..., n-1 时的最大总价值
    // 每次都在前一次的基础上加上当前能获得的最大奖励
    for (int i = 0; i < n - 2; ++i) {
        current_sum += bonuses[i];
        std::cout << " " << current_sum;
    }
    std::cout << "\n";
}

int main() {
    // 加速输入输出，对付大数据的好习惯！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(N log N) 的说。
- 读取输入、计算总权值和节点度都是 O(N) 的。
- 构建 bonuses 列表，总共会添加 n-2 个元素，也是 O(N) 的。
- 最耗时的部分是对 bonuses 列表进行排序，它的长度是 n-2，所以排序的时间复杂度是 O(N log N)。
- 最后输出结果是 O(N) 的。
- 所以总的时间复杂度由排序决定，就是 O(N log N) 啦！
空间复杂度: O(N) 的说。
- 我们需要存储节点权重 w，大小为 O(N)。
- 存储节点度 degree，大小为 O(N)。
- 存储奖励值 bonuses，大小为 O(N)。
- 所以总的空间复杂度是 O(N) 呢。

知识点与总结

这道题真是一次有趣的试炼呢！我们来总结一下学到了什么吧~

贪心思想 (Greedy Algorithm)：这道题的核心就是贪心！我们通过分析发现，每次增加可用颜色数量时，总价值的增量只取决于我们选择在哪里制造“颜色分裂”。为了让总增量最大，我们每次都选择能提供最大奖励的节点进行分裂。这种每一步都做局部最优解，最终达到全局最优的思路，就是贪心的精髓所在。
问题转化 (Problem Transformation)：我们将一个复杂的“图染色价值最大化”问题，转化为了一个简单的“收集所有奖励并排序，然后依次相加”的问题。学会从不同角度看问题，把复杂问题简化，是成为算法高手的必经之路呐！
图论基础 (Graph Theory Basics)：对树的性质，特别是“所有节点的度之和等于边数的两倍” (sum(d_v) = 2*E) 这个定理的理解，帮助我们确定了总共有 n-2 个奖励可以获取，让我们的贪心策略有了坚实的理论基础。

希望这次的题解能帮到主人哦！要对自己有信心，多思考多练习，你一定能变得更强的！加油喵~ ( ´ ▽ ` )ﾉ

D. 13th Labour of Heracles - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

基础情况：k=1 ​

核心洞察：价值从哪里来？ ​

贪心策略的诞生 ​

代码实现时间到！ ​

复杂度分析的说 ​

知识点与总结 ​