#include <iostream> #include <cstdio> #include <math.h> #include <algorithm> #include <istream> #include <string> #include <queue> #include <deque> #include <random> #include <stack> #include <set> #include <string.h> #include <map> #include <unordered_map> #include <sstream> #include <bitset> #include <fstream> #include <climits> #include <time.h> #include <cassert> using namespace std; //#include "atcoder/all" // using namespace atcoder; //#pragma GCC optimize(3) //#pragma GCC optimize("Ofast") #define endl "\n" #define int long long #define double long double #define pii pair<int, int> #define p1(x) (x).first #define p2(x) (x).second #define lc(x) ((x) << 1) #define rc(x) ((x) << 1 | 1) #define i128 __int128_t int n; int a[200300]; int dep[200030]; const int M=998244353; vector<int>g[200030]; int fa[200030][20]; inline void dfs(int u){ dep[u]=dep[fa[u][0]]+1; for(int i=1;i<=18;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int v:g[u]) if(v!=fa[u][0]){ fa[v][0]=u; dfs(v); } } inline int fak(int u,int k){ int L=18; while(L>=0){ if(k>=(1<<L)&&fa[u][L]!=0) u=fa[u][L],k-=1<<L; L--; } return u; } inline void add(int &x,int y){ x+=y; if(x>=M) x-=M; } inline int qp(int a,int x){ int res=1; while(x){ if(x&1)res=res*a%M; x>>=1; a=a*a%M; } return res; } int cnt[200300]; int s[200300]; int siz[200300]; int mx[200300]; int rt; bool vis[200300]; inline void dfssiz(int u,int fa){ siz[u]=1; dep[u]=dep[fa]+1; for(int v:g[u]) if(v!=fa&&!vis[v]){ dfssiz(v,u); siz[u]+=siz[v]; } } inline void dfsfd(int u,int fa,int S){ mx[u]=-1; for(int v:g[u])if(v!=fa&&!vis[v]){ dfsfd(v,u,S); mx[u]=max(mx[u],siz[v]); } mx[u]=max(mx[u],S-mx[u]); if(mx[u]<mx[rt])rt=u; } inline void FD(int u){ dfssiz(u,0); rt=0; dfsfd(u,0,siz[u]); } int t[200300]; inline int lb(int x){return x&-x;} inline void mod(int x,int k){ x++; if(x<=0)return ; while(x)t[x]+=k,x-=lb(x); } inline int gt(int x){ int res=0; x++; if(x<=0)return 0; while(x<=n+1)res+=t[x],x+=lb(x); return res; } inline int gt(int l,int r){return gt(r)-gt(l-1);} inline void MOD(int u,int fa,int d,int k){ mod(a[u]-d,k); for(int v:g[u]) if(!vis[v]&&v!=fa) MOD(v,u,d+1,k); } inline void ADD(int u,int fa,int d){ cnt[u]+=gt(d); for(int v:g[u]) if(!vis[v]&&v!=fa) ADD(v,u,d+1); } inline void calc(int u){ MOD(u,0,0,1); cnt[u]+=gt(0); for(int v:g[u]) if(!vis[v]){ MOD(v,u,1,-1); ADD(v,u,1); MOD(v,0,1,1); } MOD(u,0,0,-1); } inline void dfsc(int u){ vis[u]=1; calc(u); for(int v:g[u]) if(!vis[v]){ FD(v); dfsc(rt); } } inline void slv(){ mx[0]=1e9; // cin>>n; // for(int i=1;i<=n;i++) // cin>>a[i]; // for(int i=1;i<n;i++){ // int u,v; // cin>>u>>v; // g[u].push_back(v); // g[v].push_back(u); // } scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<n;i++){ int u,v; scanf("%lld%lld",&u,&v); g[u].push_back(v); g[v].push_back(u); } dfs(1); for(int i=1;i<=n;i++) s[i]=fak(i,a[i]); FD(1); dfssiz(rt,0); // int C=clock(); dfsc(rt); // cout<<(clock()-C)*1000/CLOCKS_PER_SEC<<endl; int res=0; for(int i=1;i<=n;i++){ cnt[s[i]]--; add(res,2*qp(3,cnt[s[i]])%M); } cout<<res<<endl; } inline void MT(){ int t; cin>>t; while(t--)slv(); } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // freopen("/Users/noip2019/Desktop/liuyile/样例/tree/tree.in","r",stdin); //freopen("tree.in","r",stdin); //freopen("tree.out","w",stdout); // MT(); slv(); cout.flush(); return 0; } /* 13 0 1 0 0 0 0 1 0 1 1 0 1 0 */