题目描述[链接：https://ac.nowcoder.com/acm/contest/44887/H]

思路：

   题目给出了一个由 n个有权重的节点、n−1条无向边构成的一棵树我们可以首先dfs一遍，预处理出来所有点的度数是多少。 注意根节点为1，深度为0

void dfs(int u,int f){
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j!=f){
            d[j]=d[u]+1;
            dfs(j,u);
        }
    }
}

    假若wi表示节点i得权重，那么我们可以表示出树上两点 a,b 之间的相互作用F为:

• F(a,b)=max(wa,wb)∗(da+db)

  则答案是任意节点之间的F的总和 我们可以考虑一下，对于每一个节点，他对答案的贡献是什么

         因为比较难搞的是我们不知道wi和wj谁大谁小，所以我们可以首先按照权值给他排个序。则在点i之前的所有节点j，wj都小于wi,所以我们很快可以得到最大值是wi.然后累加所有的j，就是点i的贡献的前半部分的最大值

(d[1]+d[i])+(d[2]+d[i])+(d[3]+d[i])+.....+(d[i−1]+d[i]
很容易看到对于每一个i他的max值等于他的前i-1个点的深度和sum[i-1]*(i-1)*d[i]

所以我们预处理一遍度数的前缀和数组

for(int i=1;i<=n;i++)//预处理点的前缀和深度
        sum[i]=sum[i-1]+d[p[i].yy];

accode

#include<iostream>
#include<algorithm>
#include<cstring>

#define ll long long 
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define xx first
#define yy second

using namespace std;
typedef pair<int,int> PII;
const int N=2e5+5,mod=1e9+7;
int n;
int d[N];
PII p[N];
ll sum[N];//深度的前缀和数组
int h[N],e[N<<1],ne[N<<1],idx;//邻接表
//注意e数组和ne数组都开两倍的N,否则会re
void add(int a,int b){//加边函数
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u,int f){
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j!=f){
            d[j]=d[u]+1;
            dfs(j,u);
        }
    }
}
signed main(){
    IOS;
    cin>>n;
    memset(h,-1,sizeof h);//注意初始化表头
    //pair<权重，点的标号>
    for(int i=1;i<=n;i++){
        cin>>p[i].xx;
        p[i].yy=i;
    }
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);//无向图双向建边
        add(b,a);
    }
    dfs(1,0);
    sort(p+1,p+1+n);//权重排序
    for(int i=1;i<=n;i++)//预处理点的前缀和深度
        sum[i]=sum[i-1]+d[p[i].yy];
    ll res=0;//记录答案
    for(int i=1;i<=n;i++){
        res=res+p[i].xx*(sum[i-1]+d[p[i].yy]*(i-1));
        res=res%mod;//注意取模
    }
    cout<<res%mod<<endl;
    return 0;
}