题目大意

有一棵树，需要给其所有节点染色，每个点染色所需的时间是一样的都是$1$.给每个点染色，还有一个开销“当前时间$×ci$”，$ci$ 是每个节点的一个权值。(当前时间是染完这个节点的时间) 
染色还有另一个约束条件，要染一个点必须要先染好其父节点，所以第一个染的点是根节点. 
求最小开销。

思路

基本上所有的贪心都离不开一个思路——由简到难。本题的难点在于要染一个点必须要先染好其父节点，那么先不考虑这一点去进行思考。在不考虑这一点时明显先选择权值大的先做。这里不做证明，大家都应该会。然后考虑从这个基础上去改。

我们在把基础的考虑完后就可以考虑局部问题了。从上述问题中可以看出本题大概会从权值最大的入手，那么我们不妨设权值最大的节点的父亲已经完成染色，那么必然先染这个权值最大的节点。也很明显，就是局部的上述简单问题。那么我们就可以将这两个点看成一个点了。设最大的点为 $b$，它的父亲为 $a$，那么我们考虑在局部问题上做计算。那么这个点的话费就是 $a+2b$ 了。我们考虑这个点与另外一个点 $c$ 之间的先后顺序。

当先选择 $a,b$ 时花费为 $a+2b+3c$，先选择 $c$ 的花费为 $c+2a+3b$，那我们考虑比较大小。而比较大小最方便的做法就是做差。

$a+2b+3c-(c+2a+3b)=2c-(a+b)$

那么可以看出当 $\frac{a+b}{2}$ 比 $c$ 大时应先选择前者。这是局部问题，那么我们不妨去扩展到全局。假设现由两组数已经排好了，不妨为 $a_1,a_2\cdots a_n$ 与 $b_1,b_2\cdots b_n$，考虑与上述同样的做法。

若先染 $a$，则花费为 $\sum_{i=1}^{n}a_i\times i+\sum_{i=n+1}^{n+m}b_i\times i$。

若先染 $b$，则花费为 $\sum_{i=1}^{m}b_i\times i+\sum_{i=m+1}^{m+n}a_i\times i$。

还是做差,能得到这个式子：

$\sum_{i=1}^{n}a_i\times i+\sum_{i=n+1}^{n+m}b_i\times i-(\sum_{i=1}^{m}b_i\times i+\sum_{i=m+1}^{m+n}a_i\times i)$

$=n\sum_{i=1}^{m}b_i-m\sum_{i=1}^{n}a_i$

最后我们发现，当组 $a$ 的平均数大于组 $b$ 的平均数时先选 $a$，反之先选 $b$。

然后我们可以通过这个来做了。但是找的方法还是有些困难，我们可以选择增量的方法来解决这道题。

每一次首先按照上述规则找到一个从未被选的节点，然后将它与它的父亲合并，让答案加上父亲的次数乘上当前节点的值。也就是所谓的偏移量。每一次的偏移让这个值能够成功的与父亲合并。最后结束。

代码

#include<iostream>
using namespace std;
typedef long long ll;
const ll MAXN=1005;
struct node{
    ll fa,size,sum;
    double avg;
}t[MAXN];
int main() {
    while (true){
        ll n,r;
        scanf("%lld%lld",&n,&r);
        if(n==0&&r==0){
            break;
        }
        ll ans=0;
        for (int i = 1; i <=n ; ++i) {
            scanf("%lld",&t[i].sum);
            t[i].avg=t[i].sum;
            t[i].size=1;
            ans+=t[i].sum;
        }
        for (int i = 1; i <n ; ++i) {
            ll u,v;
            scanf("%lld%lld",&u,&v);
            t[v].fa=u;
        }
        for (int i = 1; i <n ; ++i) {
            double ma=-1;
            ll u;
            for (int j = 1; j <=n ; ++j) {
                if(j!=r&&t[j].avg>ma){
                    ma=t[j].avg;
                    u=j;
                }
            }
            //上面找当前的平均值最大的那个节点。
            ll f=t[u].fa;
            ans+=t[u].sum*t[f].size;//加上偏移量
            for (int j = 1; j <=n ; ++j) {
                if(t[j].fa==u){
                    t[j].fa=f;//由于自己跟父亲合并了，所以自己的节点然要接到父亲底下。
                }
            }
            t[f].sum+=t[u].sum;
            t[f].size+=t[u].size;
            t[f].avg=double(t[f].sum*1.0/t[f].size);
            t[u].avg=-1;//代表选过了
        }
        printf("%lld\n",ans);
    }
    return 0;
}