题目描述

一颗树有 n 个节点，这些节点被标号为：1,2,3…n，每个节点 i 都有一个权值 A[i]。

现在要把这棵树的节点全部染色，染色的规则是：

根节点R可以随时被染色；对于其他节点，在被染色之前它的父亲节点必须已经染上了色。

每次染色的代价为T*A[i]，其中T代表当前是第几次染色。

求把这棵树染色的最小总代价。

输入格式
第一行包含两个整数 n 和 R ，分别代表树的节点数以及根节点的序号。

第二行包含 n 个整数，代表所有节点的权值，第 i 个数即为第 i 个节点的权值 A[i]。

接下来n-1行，每行包含两个整数 a 和 b ，代表两个节点的序号，两节点满足关系： a 节点是 b 节点的父节点。

除根节点外的其他 n-1 个节点的父节点和它们本身会在这 n-1 行中表示出来。

同一行内的数用空格隔开。

输出格式
输出一个整数，代表把这棵树染色的最小总代价。
数据范围
1≤n≤1000,
1≤A[i]≤1000

样例

输入样例：
5 1
1 2 1 2 4
1 2
1 3
2 4
3 5
输出样例：
33

算法1

(暴力枚举) $O(n^2)$

提供一种新的暴力求解思路(O(n^2))，用vector保存每次合并的序列，这样我们就可以将合并与算答案分成两部分，完全可以等全部合并完再算答案。算是比较暴力的做法吧，不过个人觉得比较好理解与实现.

时间复杂度

O(n^2)

C++ 代码

//感觉这道题的思想和其他题都好不一样啊
//让我们重理一下这个题的思路：首先考虑比较简单的情况，如果没有限制的话，我们优先将权值大的先算
//之后我们知道要想最优，越大的应该越早安排。也就是说在有条件的情况下，最大的点应该在他的父亲染色后
//立即染色才能使整体最优。这样这两个的点的顺序就确定了，因为顺序固定死了，我们就可以把他们看成一个点
//之后已推得合并后的点权应是他们的均值，然后，就暴力吧... 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010;
int f[N],n,r,a[N];
double d[N];//d[i]表示合并后以i为第一个点的序列的权值和
vector<int>v[N];
inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')ff=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*ff;
}
int main()
{
    n=read();r=read();
    for(int i=1;i<=n;++i) a[i]=read(),d[i]=a[i];
    for(int i=1;i<=n;++i) v[i].push_back(i);
    for(int i=1;i<n;++i) 
    {
        int x=read(),y=read();
        f[y]=x;
    }
    for(int i=1;i<n;++i)
    {
        double mx=-(1<<30);
        int o=0;
        for(int j=1;j<=n;++j)
            if(j!=r&&v[j].size()&&((double)(d[j]/v[j].size())>mx)) 
                mx=(double)(d[j]/v[j].size()),o=j; //找当前符合条件的最大值
        for(int j=0;j<v[o].size();++j)  v[f[o]].push_back(v[o][j]);//合并保存的序列.
        for(int j=1;j<=n;++j) if(f[j]==o) f[j]=f[o];//将父亲重置
        d[f[o]]+=d[o];v[o].clear();//更新父亲节点的总和与清空当前节点
    }
    ll ans=0;
    for(int i=0;i<v[r].size();++i) ans+=(i+1)*a[v[r][i]];//统计答案
    printf("%lld",ans);
    return 0;
}