#include<bits/stdc++.h>
#define AC return 0;
#define int long long 
#define pii pair<int,int>
#define all(tar) tar.begian(),tar.end()
const int maxx=2e5+5;
const int mod=998244353; 
using namespace std;
int n,m,t;
map<int,int>dp[maxx];
set<int>st[maxx];
int dep[maxx],a[maxx];
vector<int>G[maxx];
int minn[maxx],pos[maxx];
int anc[maxx][20];
int findfa(int x,int k){
   for(int i=0;i<20;i++){
      if(k&(1<<i))x=anc[x][i];
   }
   return x;
}
void dfs(int u,int fa){
   anc[u][0]=fa;
   dep[u]=dep[fa]+1;
   for(int i=1;(1<<i)<=dep[u];i++){
     anc[u][i]=anc[anc[u][i-1]][i-1];
   }
   int p=pos[dep[u]];
   int pa=findfa(u,p);
   st[pa].insert(dep[u]);
   dp[pa][dep[u]]=a[p];
   // cout<<u<<" "<<pa<<" "<<p<<'\n';
   for(auto v:G[u]){
      if(v==fa)continue;
      dfs(v,u);
      if(dp[u].size()>dp[v].size()){
      for(auto [x,y]:dp[v]){
         if(!st[u].count(x)){
            if(dp[u][x]+y>=a[x-dep[u]]){
               st[u].insert(x);
               dp[u][x]=a[x-dep[u]];
            }
            else dp[u][x]+=y;
         }
       }
      }else{
        auto f=dp[u];
        for(auto [x,y]:f){
          if(!st[u].count(x)){
            if(y+dp[v][x]>=a[x-dep[u]]){
               st[u].insert(x);
               dp[v][x]=a[x-dep[u]];
            }else{
               dp[v][x]+=y;
            } 
          }else dp[v][x]=y;
        }
        swap(dp[u],dp[v]);
      }
   }
   // cout<<u<<'\n';
   // for(auto [x,y]:dp[u])cout<<x<<" "<<y<<'\n';
}
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   dep[0]=-1;
   cin>>t;
   while(t--){
      cin>>n;
      for(int i=1;i<=n;i++){
         dp[i].clear();
         G[i].clear();
         st[i].clear();
      }
      for(int i=0;i<n;i++)cin>>a[i];
      pos[0]=0,minn[0]=a[0];
      for(int i=1;i<n;i++){
         minn[i]=a[i];
         pos[i]=i;
         if(minn[i]>minn[i-1]){
            minn[i]=minn[i-1];
            pos[i]=pos[i-1];
         }
      }
      for(int i=1;i<n;i++){
         int u,v;
         cin>>u>>v;
         G[u].push_back(v);
         G[v].push_back(u);
      }
      dfs(1,0);
      int ans=0;
      for(auto [x,y]:dp[1])ans+=y;
      cout<<ans<<'\n';
   }
   AC
}