#include<bits/stdc++.h> #define fst(a,b,c) for(int a=(b);a<=(c);a++) #define est(x) for(int i=hd[x],y=to[i];i;i=nt[i],y=to[i]) #define lb(x) (x&(-x)) using namespace std; const int N=5e5+100,Mod=1e9+7; int n,ans; int p[N],ord[N]; int fa[N],siz[N],hea[N],dfn[N],num,top[N]; int hd[N],to[N*2],nt[N*2],tot; int Add(int x,int y){return (x+y<0)?((x<y)?Add(x+Mod,y):Add(x,y+Mod)):((x+y>Mod)?x-Mod+y:x+y);} int Mul(int x,int y){return 1ll*x*y%Mod;} struct BITree{ int val[N]; void upd(int x,int y){while(x<=n) val[x]=Add(val[x],y),x+=lb(x); return;} int qry(int x,int y=0){while(x) y=Add(y,val[x]),x-=lb(x); return y;} }t1,t2; int read(){ char in=getchar(); int x=0; while(!isdigit(in)) in=getchar(); while(isdigit(in)) x=x*10+(in^48),in=getchar(); return x; } void add(int x,int y){ to[++tot]=y;nt[tot]=hd[x];hd[x]=tot; to[++tot]=x;nt[tot]=hd[y];hd[y]=tot; } bool cmp(int x,int y){return p[x]<p[y];} void build1(int x){ siz[x]=1; est(x){ if(y==fa[x]) continue; fa[y]=x; build1(y); siz[x]+=siz[y]; if(siz[y]>siz[hea[x]]) hea[x]=y; } return; } void build2(int x,int Fa){ dfn[x]=++num; top[x]=Fa; if(!hea[x]) return; build2(hea[x],Fa); est(x){ if(y==fa[x]||y==hea[x]) continue; build2(y,y); } return; } void ins(int x){ int sum=1,cnt=1,now=x,tmp=0,tmp_; //now=x : 第一个now不计算，因为认为now在now的轻儿子计算 // printf("x = %d\n",x); est(x){ if(y==fa[x]) continue; sum=Add(sum,Mul(Add(t1.qry(dfn[y]+siz[y]-1),-t1.qry(dfn[y]-1)),n-siz[y])); //当前子树所有节点都可以与这个子树外的点连边对点x产生贡献 sum=Add(sum,Mul(siz[y],cnt)); //点x自己产生贡献 cnt+=siz[y]; } // printf("cal son over, sum = %d\n",sum); tmp=Add(t1.qry(n),-Add(t1.qry(dfn[x]+siz[x]-1),-t1.qry(dfn[x]-1))); // 除了当前点为根的子树外所有点的正siz // printf("1. tmp = %d\n",tmp); while(now){ // printf("asd tmp = %d\n",tmp); if(now!=top[now]){ tmp=Add(tmp,-Add(t1.qry(dfn[now]-1),-t1.qry(dfn[top[now]]-1))); tmp=Add(tmp,Add(t2.qry(dfn[now]-1),-t2.qry(dfn[top[now]]-1))); //当前点的祖先在以当前点为根时贡献反siz //不计算now，因为now在now的轻儿子算过了 now=top[now]; } // printf("pod tmp = %d\n",tmp); if(now==1) break; // printf("now = %d fa = %d siz_fa = %d tmp = %d -> ",now,fa[now],siz[fa[now]],tmp); tmp_=Add(t1.qry(dfn[fa[now]]),-t1.qry(dfn[fa[now]]-1)); //fa[now]不一定已经插入，也就是说它的正siz不一定在最初被计入tmp，不需要修改 if(tmp_){ tmp=Add(tmp,-tmp_); tmp=Add(tmp,n-siz[now]); } // printf("%d\n",tmp); //t2存的是重儿子子树为根时的反siz //top[now]不是fa[top[now]]的重儿子，fa[top[now]]的反siz要特判计算 now=fa[now]; } sum=Add(sum,Mul(tmp,siz[x])); //该节点向上与包含该节点的子树所有点连边有贡献 sum=Add(sum,Mul(n-siz[x],siz[x])); //连边后点x自己有贡献 // printf("cal zuxian over, tmp = %d sum = %d\n",tmp,sum); ans=Add(ans,Mul(sum,p[x])); //算真正的贡献计入答案 t1.upd(dfn[x],siz[x]); t2.upd(dfn[x],n-siz[hea[x]]); //插入当前点在重子树节点为根时的反siz return; } int main(){ // freopen("tree.in","r",stdin); // freopen("tree.out","w",stdout); n=read(); fst(i,1,n) p[i]=read(),ord[i]=i; sort(ord+1,ord+n+1,cmp); fst(i,1,n-1) add(read(),read()); build1(1); build2(1,1); fst(i,1,n) ins(ord[i]); printf("%d\n",ans); return 0; }