#include<bits/stdc++.h> #pragma gcc optimiz(2) #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back using namespace std; typedef unsigned long long ull; typedef long long ll; const int maxn=5e5+10,mod=998244353; inline int read(){ int x=0; short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,m,dep[maxn],pw3[maxn],a[maxn],res[maxn],siz[maxn],mxs[maxn],fa[maxn][20],rt[maxn],cnt; vector<int>v[maxn]; int fa2[maxn]; bool vis[maxn]; struct SegTree { struct node { int ls,rs,sm; }d[int(3e7)+10]; #define ls(p) d[p].ls #define rs(p) d[p].rs #define sm(p) d[p].sm void upd(int l,int s,int t,int &p){ if(l<0)return; if(!p)p=++cnt;sm(p)++; if(s==t)return; int mid=s+t>>1; if(l<=mid)upd(l,s,mid,ls(p));else upd(l,mid+1,t,rs(p)); }int qry(int l,int r,int s,int t,int p){ if(!p)return 0; if(l<=s&&t<=r)return sm(p); int mid=s+t>>1,res=0; if(l<=mid)res+=qry(l,r,s,mid,ls(p));if(r>=mid+1)res+=qry(l,r,mid+1,t,rs(p)); return res; } }T; void cl(){ up(i,1,m)rt[i]=0;cnt=0; up(i,1,3e7)T.ls(i)=T.rs(i)=T.sm(i)=0; } vector<int>P; int lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); down(i,19,0)if(dep[fa[x][i]]>=dep[y])x=fa[x][i]; if(x==y)return x; down(i,19,0)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0]; }int dis(int x,int y){ return dep[x]+dep[y]-dep[lca(x,y)]*2; } void dfs1(int u){ for(int x:v[u])if(x!=fa[u][0]){ dep[x]=dep[u]+1,fa[x][0]=u;dfs1(x); } } void dfs(int u,int fa){ P.p_b(u); siz[u]=1,mxs[u]=0; for(int x:v[u])if(x!=fa&&(!vis[x])){ dfs(x,u);siz[u]+=siz[x],mxs[u]=max(mxs[u],siz[x]); } } int get_rt(int u){ P.clear();dfs(u,0); for(int x:P)mxs[x]=max(mxs[x],siz[u]-siz[x]); int mn=0;mxs[mn]=1e9; for(int x:P)if(mxs[x]<mxs[mn])mn=x; return mn; } void bd(int u){ vis[u]=1; for(int x:v[u])if(!vis[x]){ int y=get_rt(x); fa2[y]=u;bd(y); } } void init(){ n=read();m=n; up(i,1,n)a[i]=read()*2; pw3[0]=1;up(i,1,4e5)pw3[i]=pw3[i-1]*3ll%mod; up(i,1,n-1){ int x=read(),y=read(); ++m;v[m].p_b(x),v[m].p_b(y),v[x].p_b(m),v[y].p_b(m); }dep[1]=1;dfs1(1);up(i,1,19)up(j,1,m)fa[j][i]=fa[fa[j][i-1]][i-1]; bd(get_rt(1)); }void slv(){ init(); up(i,1,n){ int x=i; while(x){ T.upd(a[i]-dis(x,i),0,4e5,rt[x]); x=fa2[x]; } }up(i,1,m){ int x=i; while(x){ res[i]+=T.qry(dis(x,i),4e5,0,4e5,rt[x]); x=fa2[x]; }//cout<<"test "<<res[i]<<'\n'; }cl(); up(i,1,n){ int x=i; while(fa2[x]){ T.upd(a[i]-dis(fa2[x],i),0,4e5,rt[x]); x=fa2[x]; } }up(i,1,m){ int x=i; while(fa2[x]){ res[i]-=T.qry(dis(fa2[x],i),4e5,0,4e5,rt[x]); x=fa2[x]; } } int RES=0; up(i,1,m){ if(i<=n)(RES+=pw3[res[i]]-1)%=mod; else (RES-=pw3[res[i]]-1-mod)%=mod; }cout<<RES<<'\n'; } int main(){ // freopen("tree.in","r",stdin); // freopen("tree.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }