#include<stdio.h>
long long jis(long long w[],long long u[],long long v[],int n,int i);
long long max(long long a,long long b);
long long dfs(long long u[],long long v[],int n,int p,int f);
int main()
{
int n;
int i;
scanf("%d",&n);
long long w[n+1],u[n+1],v[n+1];
long long sum=0,num=0;
for(i=1;i<=n;i++)
{
scanf("%lld",&w[i]);
}
for(i=1;i<n;i++)
{
scanf("%lld%lld",&u[i],&v[i]);
}
for(i=1;i<n;i++)
{
sum+=jis(w,u,v,n,i);
//if(sum>=1000000007)sum-=1000000007;
}
sum=sum%1000000007;
printf("%lld",sum);
return 0;
}
long long jis(long long w[],long long u[],long long v[],int n,int i)
{
int j;
long long s1=0,s2=0,d,sum=0;
s1=dfs(u,v,n,i,-1);//起始计算点到1的距离(深度)
for(j=i+1;j<=n;j++)
{
s2=dfs(u,v,n,j,-1);//每一个匹配计算点到1的距离 (深度)
d=max(w[i],w[j]);//两点中质量的最大值
sum+=d*(s1+s2);//这个起始计算点类推下所有可能的相互作用值的和
}
return sum;
}
long long max(long long a,long long b)
{
if(b>=a)a=b;
return a;
}
long long dfs(long long u[],long long v[],int n,int p,int f)
{
int i,j,k,h=1,cnt=0;//定义辅助计算值
long long s[n];//定义缓冲数组
//从节点p点开始寻找节点1
if(p==1)
{
return 0;//若是找到节点1,则返回寻找的次数(在当前函数中为零次)
}
for(i=1;i<n;i++)//遍历所有u和v数组,寻找节点P
{
if(u[i]==p&&v[i]!=f)//且之后式子表示避免走回上一个节点
{
s[h]=v[i];//记录与节点P相连的节点
h++;
}
if(v[i]==p&&u[i]!=f)//且之后式子表示避免走回上一个节点
{
s[h]=u[i];//记录与节点相连的节点
h++;
}
}
h--;//出循环后,把h上多加的一个1减去
if(h==0)//s数组为空表示已无下一级连接的节点
{
return -1;//无节点直接返回-1表示此路不通,把进函数前加的计数给减去
}
for(j=h;j>0;j--)//遍历与节点p相连的所有节点
{
cnt++;//每进入函数一次,表示寻找一次,计数加一
cnt+=dfs(u,v,n,s[j],p);//以与节点p相连的点做新的节点p,做新一轮寻找
if(cnt!=0)break;//若返回值不为0,表示此路已通,因为只有唯一路径,所以跳出循环
}
return cnt;//返回寻找的次数表示深度
}
全部评论
(1) 回帖