问题分析

题目要求我们计算给一棵树的节点上色的最小总成本。每个节点的上色成本由其“上色成本因子”$C_i$ 和完成上色的时间 $F_i$ 决定，具体公式为 $C_i \times F_i$。Bob 必须先给父节点上色，才能给子节点上色。因此，我们需要找到一种上色顺序，使得总成本最小。

难点应对

1. 上色顺序的约束：Bob 必须先给父节点上色，才能给子节点上色。这意味着我们需要从根节点开始，逐步向上色子节点扩展。
2. 成本计算的动态性：每个节点的上色成本不仅取决于其成本因子，还取决于上色的时间顺序。我们需要动态地调整上色顺序以最小化总成本。

解题思路

1. 初始化：

   • 读取每个节点的上色成本因子 $C_i$。
   • 构建父子关系，记录每个节点的父节点。

2. 贪心策略：

   • 从根节点开始，每次选择当前未上色的节点中成本因子最大的节点进行上色。
   • 在上色过程中，将子节点的上色成本因子更新为其父节点的平均成本因子。

3. 动态更新：

   • 每次上色后，更新父节点的子节点数量和总成本。
   • 使用路径压缩优化查找父节点的过程。

4. 计算总成本：

   • 按照上色顺序累加每个节点的成本。

代码实现

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 1005

int n, r; // n: 节点数量，r: 根节点编号
double c[N]; // 每个节点的上色成本因子
int nxt[N], la[N], num[N], fa[N]; // nxt: 链表下一个节点，la: 链表最后一个节点，num: 子树节点数量，fa: 父节点
double d[N]; // 保存初始的上色成本因子
double tot[N]; // 子树的总成本
bool vis[N]; // 标记节点是否已经被上色

// 主函数，用于计算最小上色成本
void color_a_tree()
{
    // 初始化每个节点的上色成本因子和链表结构
    for (int i = 1; i <= n; i++)
    {
        scanf("%lf", &c[i]); // 读取每个节点的上色成本因子
        nxt[i] = i; // 初始时，每个节点的下一个节点是自己
        la[i] = i; // 初始时，每个节点的最后一个节点是自己
        num[i] = 1; // 初始时，每个子树只有一个节点
        tot[i] = c[i]; // 初始时，每个子树的总成本是其自身的成本因子
    }
    memcpy(d, c, sizeof(d)); // 复制初始成本因子到 d 数组

    // 构建父子关系
    for (int i = 1, a, b; i < n; i++)
    {
        scanf("%d%d", &a, &b); // 读取父子关系
        fa[b] = a; // 父节点信息
    }

    // 初始化访问标记数组
    memset(vis, 0, sizeof(vis));

    // 逐步上色，每次选择未上色的节点中成本因子最大的节点
    for (int i = 1; i < n; i++)
    {
        int p; // 当前选择的节点
        double k = 0; // 用于记录当前最大成本因子
        // 找到未上色的节点中成本因子最大的节点
        for (int j = 1; j <= n; j++)
            if (j != r && !vis[j] && c[j] > k)
            {
                k = c[j];
                p = j;
            }

        // 获取父节点，并使用路径压缩优化查找过程
        int f = fa[p];
        while (vis[f]) fa[p] = f = fa[f]; // 路径压缩

        // 更新父节点的链表结构和子树信息
        nxt[la[f]] = p; // 将当前节点连接到父节点的链表末尾
        la[f] = la[p]; // 更新父节点链表的最后一个节点
        num[f] += num[p]; // 更新父节点的子树节点数量
        tot[f] += tot[p]; // 更新父节点的子树总成本
        c[f] = tot[f] / num[f]; // 更新父节点的平均成本因子

        // 标记当前节点已上色
        vis[p] = 1;
    }

    // 计算总上色成本
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += i * d[r]; // 累加上色成本
        r = nxt[r]; // 更新根节点为下一个上色的节点
    }
    printf("%d\n", ans); // 输出最小总上色成本
}

int main()
{
    // 处理多个测试用例
    while (scanf("%d%d", &n, &r) == 2 && n && r) 
    {
        color_a_tree(); // 调用主函数计算最小上色成本
    }
    return 0;
}

代码解析

以下是代码的详细解析：

初始化部分

for (int i = 1; i <= n; i++)
{
    scanf("%lf", &c[i]);
    nxt[i] = i; la[i] = i; num[i] = 1; tot[i] = c[i];
}
memcpy(d, c, sizeof(d));
for (int i = 1, a, b; i < n; i++)scanf("%d%d", &a, &b), fa[b] = a;

• 读取每个节点的上色成本因子 $C_i$。
• 初始化每个节点的链表结构（nxt 和 la），以及子节点数量（num）和总成本（tot）。
• 读取父子关系，构建树的结构。

上色过程

for (int i = 1; i < n; i++)
{
    int p;
    double k = 0;
    for(int j=1;j<=n;j++)
        if (j != r && !vis[j] && c[j] > k)
        {
            k = c[j];
            p = j;
        }
    int f = fa[p];
    while (vis[f]) fa[p] = f = fa[f]; // 路径压缩
    nxt[la[f]] = p;
    la[f] = la[p];
    num[f] += num[p];
    tot[f] += tot[p];
    c[f] = tot[f] / num[f];
    vis[p] = 1;
}

• 每次选择未上色的节点中成本因子最大的节点 p。
• 使用路径压缩找到 p 的父节点 f。
• 更新父节点的链表结构、子节点数量和总成本。
• 更新父节点的成本因子为当前子树的平均成本因子。

计算总成本

int ans = 0;
for (int i = 1; i <= n; i++)
{
    ans += i * d[r];
    r = nxt[r];
}
printf("%d\n", ans);

• 按照上色顺序累加每个节点的成本。
• d[r] 是根节点的初始成本因子，r 通过 nxt 逐步更新为下一个上色的节点。

总结

本题的关键在于利用贪心策略动态调整上色顺序，并通过路径压缩优化查找父节点的过程。通过这种方式，我们可以高效地计算出最小总上色成本。