#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define rep2(i, l, r) for (ll i = l; i < r; i++)

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;

#define all(A) A.begin(), A.end()
#define elif else if
using pii = pair<ll, ll>;

bool chmin(auto &a, const auto &b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, const auto &b) { return a < b ? a = b, 1 : 0; }

struct IOSetup {
  IOSetup() {
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
} iosetup;

template <class T>
void print(vector<T> a) {
  for (auto x : a) cerr << x << ' ';
  cout << endl;
}

void print(auto x) { cout << x << endl; }

template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
  cout << head << ' ';
  print(forward<Tail>(tail)...);
}

// template <class S, auto op, auto e>
template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
  int sz, N;
  vector<S> d;

  segtree() : segtree(0) {}                       // 必要に応じて
  segtree(int n) : segtree(vector<S>(n, e())) {}  // 必要に応じて
  segtree(vector<S>& v) {
    sz = 1;
    N = v.size();
    while (sz < N) sz <<= 1;
    d.assign(2 * sz, e());
    rep(i, N) d[i + sz] = v[i];
    for (int k = sz - 1; k > 0; k--) d[k] = op(d[2 * k], d[2 * k + 1]);
  }

  void set(int k, S x) {
    k += sz;
    d[k] = x;
    while (k >>= 1) {
      d[k] = op(d[2 * k], d[2 * k + 1]);
    }
  }

  S prod(int l, int r) {
    S sml = e(), smr = e();
    for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
      if (l & 1) sml = op(sml, d[l++]);
      if (r & 1) smr = op(d[--r], smr);
    }
    return op(sml, smr);
  }
};

struct LCA {
  int n;
  vvi G, st;
  vi dep, S, FS;

  LCA()=default;

  int LOG(int i) { return 31 - __builtin_clz(i); }

  LCA(int n, vvi &G, int root) : n(n), G(G) {
    dep.assign(n, -1);
    FS.resize(n);
    dep[root] = 0;
    dfs(root, -1);
    int L = S.size();
    st.resize(LOG(L) + 1);
    st[0] = S;
    int b = 1;
    rep(i, LOG(L)) {
      int sz = st[i].size() - b;
      st[i + 1].resize(sz);
      rep(j, sz) {
        int u = st[i][j];
        int v = st[i][j + b];
        st[i + 1][j] = (dep[u] <= dep[v]) ? u : v;
      }
      b *= 2;
    }
  }

  void dfs(int v, int p) {
    FS[v] = S.size();
    S.push_back(v);
    for (auto u : G[v]) {
      if (u != p) {
        dep[u] = dep[v] + 1;
        dfs(u, v);
        S.push_back(v);
      }
    }
  }

  int lca(int u, int v) {
    int x = FS[u], y = FS[v];
    if (x > y) swap(x, y);
    int l = LOG(y - x + 1);
    int px = st[l][x], py = st[l][y - (1 << l) + 1];
    return (dep[px] <= dep[py]) ? px : py;
  }
};

ll inf=1LL<<60;

ll op(ll a,ll b){return min(a,b);}
ll e(){return inf;}

void solve(){
  int n;
  cin>>n;
  vll a(n);
  rep(i,n)cin>>a[i];
  vvi edge(n);
  rep(i,n-1){
    int u,v;
    cin>>u>>v;
    u--;v--;
    edge[v].push_back(u);
    edge[u].push_back(v);
  }
  LCA lca(n,edge,0);

  vi first(n),dep(n,-1);
  {
    vi stc={0};
    dep[0]=0;
    int num=0;
    while(!stc.empty()){
      int v=stc.back();
      stc.pop_back();
      if(v>=0){
        first[v]=num;
        num++;
        for(auto u:edge[v]){
          if(dep[u]==-1){
            dep[u]=dep[v]+1;
            stc.push_back(~u);
            stc.push_back(u);
          }
        }
        reverse(all(edge[v]));
      }
      else{
        v=~v;
        num++;
      }
    }
  }

  vvi G(n);

  int root;

  auto query=[&](vi vs)->void{
    int k=vs.size();
    vector<pair<int,int>>res;
    for(auto v:vs){
      res.push_back({first[v],v});
    }
    sort(res.begin(),res.end());
    vi s;
    for(auto [_,v]:res)s.push_back(v);

    vi stc;
    stc.push_back(s[0]);
    G[s[0]].clear();
    rep(i,k-1){
      int w=lca.lca(s[i],s[i+1]);
      if(w!=s[i]){
        int last=stc.back();
        stc.pop_back();
        while(!stc.empty()&&dep[w]<dep[stc.back()]){
          G[stc.back()].push_back(last);
          last=stc.back();
          stc.pop_back();
        }

        if((stc.size()==0)||stc.back()!=w){
          stc.push_back(w);
          s.push_back(w);
          G[w].push_back(last);
        }
        else{
          G[w].push_back(last);
        }
      }
      stc.push_back(s[i+1]);
      G[s[i+1]].clear();
    }
    int sz=stc.size();
    for(int i=0;i<sz-1;i++){
      G[stc[i]].push_back(stc[i+1]);
    }
    root=stc[0];
  };

  vvi dep_list(n);
  rep(i,n)dep_list[dep[i]].push_back(i);

  segtree<ll,op,e>seg(a);

  ll ans=a[0];

  vll dp(n,inf),memo(n,-1);
  rep2(i,1,n){
    vi vs=dep_list[i];
    if(vs.size()==0)continue;
    vs.push_back(0);
    query(vs);
    assert(root==0);
    vector<array<int,3>>todo;
    todo.push_back({1,root,-1});
    todo.push_back({0,root,-1});
    while(!todo.empty()){
      auto [t,v,p]=todo.back();
      todo.pop_back();
      if(t==0){
        dp[v]=0;
        for(auto u:G[v]){
          todo.push_back({1,u,v});
          todo.push_back({0,u,v});
        }
      }
      else{
        if(v==0){
          ans+=min(a[i],dp[v]);
          continue;
        }
        int d1=dep[p];
        int d2=dep[v];
        if(G[v].size()==0)dp[v]=inf;
        ll mn=seg.prod(i-d2,i-d1);
        dp[v]=min(dp[v],mn);
        dp[p]+=dp[v];
      }
    }
    // print(dp);
  }
  cout<<ans<<"\n";
}

int main(){
  int t;
  cin>>t;
  rep(i,t)solve();
}