给树染色
题意
一颗树有 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)
令其小于0 则 c < a + b 2 c < \dfrac {a+b}{2} c<2a+b 即a b两个节点的平均值大于 c 时，先对 a b 进行染色代价较小
所以我们在考虑点的染色顺序时，将 a b 看成一个点，其权值为 a b 的均值。
进一步推广：有两组点 a 1 , a 2 , a 3 … a n a_1,a_2,a_3 \dots a_n a1,a2,a3…an 和 b 1 , b 2 , b 3 … b n b_1,b_2,b_3 \dots b_n b1,b2,b3…bn 当第一组点的权值（平均值）大于第二组的权值（平均值）时，先染第一组点。
所以最终做法为：每次找出当前权值最大的非根节点，将其染色顺序排在其父节点之后的位置，然后将该点合并进父节点，并更新父节点的权值，直到将所有的点都合并进根节点为止。
在进行点的合并时进行权值的更新。例如有两组点 x , y x,y x,y 将 x x x 合并进 y y y 中，因为 x x x 中的所有点都排在 y y y 中的最后一个点后染色，所以 x x x 中点的权值都要乘以一个偏移量 k k k ， k k k 为 y y 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;
}