思路

我最近一直在跟着李煜东写的算法进阶教程写题。这道题的限制条件有以下几个：

• 必须在父节点染色的情况下才能进行对子节点的染色。
• 要求最小的染色代价。

思考这两个条件，我们可以得出，只要我们优先选择平均损耗最大的子树进行染色，我们就可以得到最优解；另外，明显的是，如果我们给一个父节点染色，那么它的子节点中平均损耗最大的节点就会被优先染色。

为了让更多人理解，我打算分段代码来解释这个解法。

代码块

struct node
{
    int tim, cost, fat;
    double w;
} nums[maxn];

我们定义了一个数据结构，分别定义了次数、花费、父节点和平均权值。

int find_max()
{
    double val = 0;
    int id = 1;
    for (int i = 1; i <= n; i++)
        if (i != root && nums[i].w > val)
            id = i, val = nums[i].w;
    return id;
}

为了找到平均权值最大的节点，我们采用一种\(O(n)\)的方式来进行查找，我相信会有更优的解法，恕我只能在这写下其中一种。其中注意，我们在查找过程中需要把\(root\)节点排除在外。

int main()
{
    while (scanf("%d%d", &n, &root) && n != 0)
    {
        long long ans = 0;
        for (int i = 1; i <= n; i++)
            scanf("%d", &nums[i].cost), nums[i].w = nums[i].cost, nums[i].tim = 1, ans += nums[i].cost;
        for (int i = 1; i < n; i++)
            scanf("%d%d", &x, &y), nums[y].fat = x;
        for (int i = 1; i < n; i++)
        {
            int idx = find_max();
            nums[idx].w = 0;
            ans += nums[idx].cost * nums[nums[idx].fat].tim;
            for (int j = 1; j <= n; j++)
                if (nums[j].fat == idx)
                    nums[j].fat = nums[idx].fat;
            nums[nums[idx].fat].cost += nums[idx].cost;
            nums[nums[idx].fat].tim += nums[idx].tim;
            nums[nums[idx].fat].w = double(nums[nums[idx].fat].cost) / nums[nums[idx].fat].tim;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

接下来就是主函数了。我们先来看循环内的代码。我们首先是读入和初始化了\(nums[]\)数组，把损耗、次数初始化，并且向答案加上每个点的损耗（这是必须要加上的）。之后读入边。之后，我们开始进行计算。我们的范围在\([1,n)\)内，因为我们之前已经给答案加上了所有节点的基础值，而且总有一个结点的损耗值只需要乘上一，所以我们就可以把范围定在这个区间内。

我们寻找平均损耗最大的节点，并且将其损耗赋为\(0\)，以便之后的查找会将其排除。之后我们把其子节点们全部合并到点\(idx\)的父亲节点上。之后，我们将两个节点的一些属性进行合并。

最后输出，得到答案。完整代码：

// POJ2054.cpp
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1010;
int n, root, x, y;
struct node
{
    int tim, cost, fat;
    double w;
} nums[maxn];
int find_max()
{
    double val = 0;
    int id = 1;
    for (int i = 1; i <= n; i++)
        if (i != root && nums[i].w > val)
            id = i, val = nums[i].w;
    return id;
}
int main()
{
    while (scanf("%d%d", &n, &root) && n != 0)
    {
        long long ans = 0;
        for (int i = 1; i <= n; i++)
            scanf("%d", &nums[i].cost), nums[i].w = nums[i].cost, nums[i].tim = 1, ans += nums[i].cost;
        for (int i = 1; i < n; i++)
            scanf("%d%d", &x, &y), nums[y].fat = x;
        for (int i = 1; i < n; i++)
        {
            int idx = find_max();
            nums[idx].w = 0;
            ans += nums[idx].cost * nums[nums[idx].fat].tim;
            for (int j = 1; j <= n; j++)
                if (nums[j].fat == idx)
                    nums[j].fat = nums[idx].fat;
            nums[nums[idx].fat].cost += nums[idx].cost;
            nums[nums[idx].fat].tim += nums[idx].tim;
            nums[nums[idx].fat].w = double(nums[nums[idx].fat].cost) / nums[nums[idx].fat].tim;
        }
        printf("%lld\n", ans);
    }
    return 0;
}