题意：任务是在一棵树状结构中以最小的成本完成所有节点的染色，如果要染一个节点那么他的父节点必须已经染过色。染色成本取决于节点的染色成本因子与染色时间。通过分析得出正确的染色策略，并给出了一种有效的算法实现。
错误的贪心策略：对于一个节点的子节点 染过这个结点之后 就递归到他的所有子树节点中权值最大的点所在的子树 但是这种贪心策略是错误的 比如 一个节点有左右子树 子树中最大的节点在右子树 但是左、右子树的节点个数远远大于左子树的节点个数但是右子树中的节点最大值又仅仅大于左子树节点最大值+1 或者只大于一点 这个最大值又位于非常深的位置 那么按照我这种贪心策略 也就是先染右子树 那么这种策略就会使左子树的节点都等待右子树节点的个数的时间 那么就会使答案更大 所以这种贪心策略是错误的
正确的贪心策略：树中除根节点外最大的点，一定会在它的父节点被染色后立即染色。 对于两个点集A，B 假设先选A，会让B中所有点“等待”ca次选点 若要选择A更优，则有w[b]cnt1[a] < w[a]cnt1[b],便得到了w[b]/cnt1[b] < w[a]/cnt1[a]，即A中点权的平均数要较大。那么我们的贪心策略便可以变为：树上所有点集中点权算术平均数最大的点集A的父亲F被选择后， 应该立刻选择A,（具体w，cnt1数组含义看代码即可）。
题解：首先dfs处理出来每个子树的节点个数和权值 然后在合并的过程中对于一个节点的所有子节点 找到权值平均数最大的子节点 记录贡献并把这个子节点合并给当前他的父节点 即可时间复杂度 O(n²)
const int N = 1010;
int mx[N], w[N], c[N], cnt[N], ans[N];
vi G[N];
bool cmp(pii a, pii b) {return 1LL * w[a.first] * cnt[b.first] > 1LL * w[b.first] * cnt[a.first];
}
void dfs0(int u, int fa) {mx[u] = fa;cnt[u] = 1;w[u] = c[u];rep0(i, G[u].size()) {int v = G[u][i];if (v == fa) {continue;}dfs0(v, u);cnt[u] += cnt[v];w[u] += w[v];}
}
void dfs1(int u, int fa) {if (!cnt[u]) {ans[u] = 0;return;}vi p(cnt[u] + 1), s(cnt[u] + 1), cnt1(cnt[u] + 1), vis(cnt[u] + 1);rep1(i, cnt[u]) {p[i] = mx[i];s[i] = c[i];cnt1[i] = 1;vis[i] = 0;}i64 res = 0;rep1(i, cnt[u]) { res += c[i]; }rep1(i, cnt[u] - 1) {int idx = -1;double mn = -1e300;rep1(j, cnt[u]) {if (j == u || vis[j]) {continue;}double v = (double)s[j] / (double)cnt1[j];if (v > mn) {mn = v;idx = j;}}if (idx == -1) {break;}vis[idx] = 1;res += s[idx] * cnt1[p[idx]];rep1(j, cnt[u]) {if (p[j] == idx) {p[j] = p[idx];}}s[p[idx]] += s[idx];cnt1[p[idx]] += cnt1[idx];}ans[u] = res;}
void solve() {int m, R;while (cin >> m >> R) {if (m == 0 && R == 0) {break;}rep1(i, m) {G[i].clear();cnt[i] = w[i] = ans[i] = 0;}rep1(i, m) { cin >> c[i]; }rep0(i, m - 1) {int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}dfs0(R, -1);dfs1(R, -1);cout << ans[R] << "\n";}
}