题意

和UVA1205是同一题，在洛谷上是紫题

有一棵树，需要给其所有节点染色，每个点染色所需的时间是一样的都是

$思路$

$这道题显然对于每一个可选的子节点选最重的的贪心思路是错误的$

$就有点类似动态规划了不过不DP也是可以贪心出来的。但是这个策略比较麻烦。大致思路就是父节点和子节点经过一些操作合并，合并之后贪心就是没问题的了。$

$不过我一开始自己的思路就是类似并查集+贪心的，不是合并（虽然差不多），就是全局贪心，把所有的点的权值排序，然后最大到最小的所有点慢慢并查集搜回去，直到所有点被处理过，也应该是可以的吧？但是时间复杂度肯定不行，于是就看李煜东的代码了（颓）。$

Code

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

#define N 1005

int n, r;
double c[N];
int nxt[N], la[N], num[N],fa[N];
double d[N],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));
    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];//getfather
        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
", ans);
}

int main()
{
    while (scanf("%d%d", &n, &r) == 2 && n && r) color_a_tree();
    return 0;
}