#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,p[N],ord[N],fa[N],siz[N],hea[N],dfn[N],num,top[N],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的轻儿子计算 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]; } tmp=Add(t1.qry(n),-Add(t1.qry(dfn[x]+siz[x]-1),-t1.qry(dfn[x]-1))); // 除了当前点为根的子树外所有点的正siz while(now){ 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]; } if(now==1)break; 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]); } //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自己有贡献 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(){ 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",ans); return 0; }