给树染色

1 题目描述

一颗树有 $n$ 个节点，这些节点被标号为：$1, 2, 3 \dots n$，每个节点 $i$ 都有一个权值 $A[i]$。

现在要把这棵树的节点全部染色，染色的规则是：

根节点 $R$ 可以随时被染色；对于其他节点，在被染色之前它的父亲节点必须已经染上了色。

每次染色的代价为 $T \times A[i]$，其中 $T$ 代表当前是第几次染色。

求把这棵树染色的最小总代价。

输入格式

第一行包含两个整数 $n$ 和 $R$，分别代表树的节点数以及根节点的序号。

第二行包含 $n$ 个整数，代表所有节点的权值，第 $i$ 个数即为第 $i$ 个节点的权值 $A[i]$。

接下来 $n-1$ 行，每行包含两个整数 $a$ 和 $b$，代表两个节点的序号，两节点满足关系：$a$ 节点是 $b$ 节点的父节点。

除根节点外的其他 $n-1$ 个节点的父节点和它们本身会在这 $n-1$ 行中表示出来。

同一行内的数用空格隔开。

输出格式

输出一个整数，代表把这棵树染色的最小总代价。

数据范围

$1 \le n \le 1000$, $1 \le A[i] \le 1000$。

输入样例：

1
2
3
4
5
6

5 1
1 2 1 2 4
1 2
1 3
2 4
3 5

输出样例：

1

33

2 解析

如果没有 “先选父节点” 的限制，每轮可以任意选择一个点染色，那么本题就是一个 排序不等式 的结论题。

考虑加了这一限制后，如何处理本问题，易发现一个简单性质：

对含有最大权值的结点，对其父节点染色后，下一个染色对象必然是他（排序不等式易证）。

既然该结点与他的父节点的染色顺序是相邻的，根据该性质，我们可以将这两个点 合并 成一个点，合并后的新结点权值，为两个点权值的平均值。

例如有权值 $x, y, z$ 的三个点，其中 $x, y$ 染色是连续进行的，那么有两种染色方案：

1. 先 $z$ 后 $x, y$，其代价为：$z + 2x + 3y$
2. 先 $x, y$ 后 $z$，其代价为：$x + 2y + 3z$

做差易得：$x + y - 2z$。若 $z < \frac{x+y}{2}$ 时，$z$ 先于 $x, y$；若 $z > \frac{x+y}{2}$ 时，$x, y$ 先于 $z$。

因此，$x, y, z$ 三点的染色顺序可以转化为 $\frac{x+y}{2}, z$ 两点的染色顺序。

将上述简单情况推广到一般情况，假设有两组点 $a_1, \dots, a_n$ 和 $b_1, \dots, b_m$ 进行染色：

1. 先 $a_i$ 后 $b_i$，其代价为：$\sum_{i=1}^n i a_i + \sum_{i=1}^m (i+n) b_i$
2. 先 $b_i$ 后 $a_i$，其代价为：$\sum_{i=1}^m i b_i + \sum_{i=1}^n (i+m) a_i$

做差易得：$n \sum_{i=1}^m b_i - m \sum_{i=1}^n a_i$。若 $\frac{\sum_{i=1}^m b_i}{m} > \frac{\sum_{i=1}^n a_i}{n}$，则 $b_i$ 先于 $a_i$；反之后于。

由此得到一个 “等效权值” 的算法：记录每个点是由多少个点合并而成的，一个点的 “等效权值” 定义为：

最终做法是：不断在树中找到 “等效权值” 最大的点 $p$，让其与其父节点 $fa$ 合并，并让 $p$ 染色顺序接在 $fa$ 之后，直到树中只剩下一个点为止，合并完成。根据合并过程中的染色顺序，计算最终的代价。

关于答案统计

我这里给出一个完全不同的思路，不用像 y 总那样推导出每次便宜后的总值，思维量会稍微小一点。

不难发现 “等效权值” 点所代表的一类点可以看做一个集合，那么不妨用 带权并查集 来维护每个等效权值点：

1. 点权：在根节点维护这个集合的 “等效权值” 以及集合的大小。
2. 边权：用边权维护在这个集合中该节点的次序。

这样最后整个树中只会有一个并查集，因此每个点到根的路径长，就是他在染色过程中的次序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

int find(int u) 
{
    if (p[u] != u)
    {
        int t = find(p[u]);
        d[u] += d[p[u]];
        p[u] = t;
    }
    return p[u];
}
void merge(int a, int b) 
{
    p[a] = b;
    d[a] += siz[b];
    siz[b] += siz[a];
}
int get_maxid()
{
    double maxv = 0;
    int id = -1;
    for (int i = 1; i <= n; i ++ )
    {
        if (i != root && find(i) == i && v[i] > maxv)
        {
            id = i;
            maxv = v[i];
        }
    }
    return id;
}

int main()
{
    cin >> n >> root;
    for (int i = 1; i <= n; i ++ )
        cin >> w[i], v[i] = w[i], d[i] = 0, p[i] = i, siz[i] = 1;

    for (int i = 1, a, b; i < n; i ++ )
        cin >> a >> b, fa[b] = a;

    for (int i = 1; i < n; i ++ )
    {
        int t = get_maxid(), father = find(fa[t]);
        v[father] = (v[t] * siz[t] + v[father] * siz[father]) / (siz[t] + siz[father]);
        merge(t, father);
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        res += (d[i] + 1) * w[i];
    cout << res << endl;
    return 0;
}

3 相关题解