给树染色
题意
一颗树有 n 个节点，这些节点被标号为：1,2,3…n，每个节点 ii 都有一个权值 A[i]。
现在要把这棵树的节点全部染色，染色的规则是：
根节点 R 可以随时被染色；对于其他节点，在被染色之前它的父亲节点必须已经染上了色。
每次染色的代价为 T×A[i]，其中 TT 代表当前是第几次染色。
求把这棵树染色的最小总代价。
思路
比较容易想到的贪心思路为，每次找到还未染色的权值最大的节点进行染色。但是对于这样的一棵树：有一个节点的权值较小，但是它的子节点权值都非常大，另一个节点的权值较大，但是没有子节点。上述的贪心算法显然不是最优解。
题目中提到，一个节点被染色之前其父亲节点必须已经染上了色。我们可以想到类似于上述贪心算法的一个算法：若一个节点被染色了，那么它的权值最大的子节点一定在它之后被染色。
假设一个节点为 a 其权值最大的子节点为 b ，另外一个节点为 c 那么有以下两种染色方案。
先给a b染色，再给 c 染色
代价为：a + 2*b + 3*c
先给 c 染色，再给a b 染色
代价为 c + 2*a + 3*b
(a + 2*b + 3*c) - (c + 2*a + 3*b) = 2*c - (a + b)
所以我们在考虑点的染色顺序时，将 a b 看成一个点，其权值为 a b 的均值。
进一步推广：有两组点 a 1 , a 2 , a 3 … a n 和 b 1 , b 2 , b 3 … b n
当第一组点的权值（平均值）大于第二组的权值（平均值）时，先染第一组点。
所以最终做法为：每次找出当前权值最大的非根节点，将其染色顺序排在其父节点之后的位置，然后将该点合并进父节点，并更新父节点的权值，直到将所有的点都合并进根节点为止。
在进行点的合并时进行权值的更新。例如有两组点x , y 将 x合并进 y中，因为 x 中的所有点都排在 y中的最后一个点后染色，所以 x 中点的权值都要乘以一个偏移量 k，k 为 y 中 点的数量。
代码
#include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define mod 1000000007 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) using namespace std; typedef long long LL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } const int N = 1000 + 10; int n, root; struct Node { int p; // 当前节点的父亲节点 int s; // 点集的大小 int v; //当前点集的权值 double avg; //当前点集的平均值 }node[N]; int find() { // 找到当前还未染色的平均值最大的点集 int res = 0; double avg = 0.0; for (int i = 1; i <= n; ++i) { if (i != root && node[i].avg > avg) { avg = node[i].avg; res = i; } } return res; } void solve() { cin >> n >> root; int ans = 0; for (int i = 1; i <= n; ++i) { cin >> node[i].v; node[i].avg = node[i].v; node[i].s = 1; ans += node[i].v; //由题意，肯定是根节点作为第一个染色的节点，剩下的点的染色顺序全部排在根节点之后，所以也会产生一个偏移量为根节点的点集大小，为1，所以要加上所有非根节点的权值，根节点为第一个染色的，所以也要加上根节点的权值，即每个点的权值都要加上一次。 } for (int i = 1; i <= n - 1; ++i) {// 记录点的父子关系 int a, b; cin >> a >> b; node[b].p = a; } for (int i = 1; i <= n - 1; ++i) { int p = find(); // 找到当前平均值最大的点 int father = node[p].p; // 平均值最大的点的父节点 ans += node[p].v * node[father].s; // 答案加上自己点的权值 * 偏移量 node[p].avg = -1; // 置成 -1 相当于标记已经染色过了 for (int j = 1; j <= n; ++j) { if (node[j].p == p) node[j].p = father; } // 将子节点与父节点缩成一个点 node[father].v += node[p].v; node[father].s += node[p].s; //更新缩点后的平均权值 node[father].avg = (double)node[father].v / node[father].s; } cout << ans << endl; } signed main() { // int t; cin >> t; // while (t--) solve(); return 0; }
