// Hydro submission #678f58333e10c2b5101fb1f3@1737447476008
#include <bits/stdc++.h>

void Freopen() {
    freopen("", "r", stdin);
    freopen("", "w", stdout);
}

using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10, inf = 1e9, mod = 998244353;

int t;
int n, tot;
long long ans;

int a[N];

vector< int> G[N], E[N], D[N];

int Log[N];

void init( int n) {
    ans = tot = Log[1] = 0;

    for ( int i = 2; i <= n; i ++)
        Log[i] = Log[i >> 1] + 1;

    for ( int i = 1; i <= n; i ++)
        G[i].clear(), D[i].clear();
}

struct S_T {
    int f[N][18];

    void init_mi( int n, int a[]) {
        for ( int i = 1; i <= n; i ++) f[i][0] = a[i];
        
        for ( int j = 1; j <= Log[n]; j ++) 
            for ( int i = 1; i + (1 << j) - 1 <= n; i ++)
                f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    }

    int ask_mi( int l, int r) {
        int s = Log[r - l + 1];
        return min(f[l][s], f[r - (1 << s) + 1][s]);
    }
} st;

int fa[N], siz[N], dep[N], son[N];
int top[N], dfn[N];

long long dp[N];

int lxr[3 * N], len;

int cmp( int a, int b) {
    return dfn[a] < dfn[b];
}

void dfs1( int u, int fu) {
    fa[u] = fu, siz[u] = 1, dep[u] = dep[fu] + 1, son[u] = 0;
    D[dep[u]].push_back(u);

    for ( auto v : G[u]) {
        if (v == fu) continue ;

        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[son[u]] < siz[v]) son[u] = v;
    }
}

void dfs2( int u, int topt) {
    top[u] = topt, dfn[u] = ++ tot;

    if (son[u]) dfs2(son[u], topt);

    for ( auto v : G[u])
        if (v != fa[u] && v != son[u]) dfs2(v, v);
}

int lca( int u, int v) {
    int tu = top[u], tv = top[v];

    while (tu != tv) {
        if (dep[tu] < dep[tv]) swap(u, v), swap(tu, tv);

        u = fa[tu], tu = top[u];
    }

    return dep[u] < dep[v] ? u : v;
}

void build( const vector< int> & vec, int D) {
    int len = 0, k = vec.size();

    for ( int i = 1; i <= k; i ++)
        lxr[++ len] = vec[i - 1];

    sort(lxr + 1, lxr + len + 1, cmp), len = unique(lxr + 1, lxr + len + 1) - lxr - 1;

    for ( int i = 1; i < k; i ++) lxr[++ len] = lca(lxr[i], lxr[i + 1]);

    lxr[++ len] = 1;
    sort(lxr + 1, lxr + len + 1, cmp), len = unique(lxr + 1, lxr + len + 1) - lxr - 1;

    for ( int i = 1; i < len; i ++) {
        int u = lca(lxr[i], lxr[i + 1]);
        E[u].push_back(lxr[i + 1]);
    }

    function< void( int)> dfs = [&]( int u) {
        if (! E[u].size()) {
            dp[u] = st.ask_mi(1, D);

            return ;
        }

        dp[u] = 0;

        for ( auto v : E[u]) {
            dfs(v);
            dp[u] += dp[v];
        }

        dp[u] = min(dp[u], 1ll * st.ask_mi(D - dep[u] + 1, D));
    } ;

    dfs(1);
    for ( int i = 1; i <= len; i ++)
        E[lxr[i]].clear();

    ans += dp[1];
}

void solve() {
    cin >> n;
    init(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);
    }

    st.init_mi(n, a);
    dfs1(1, 0), dfs2(1, 1);
    
    for ( int i = 1; i <= n; i ++) {
        if (! D[i].size()) continue ;

        build(D[i], i);
    }

    cout << ans << '\n';
}

signed main() {
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> t;
    while (t --) solve();
    
    return 0;
}

answer.code: In function ‘void dfs1(int, int)’:
answer.code:64:16: error: ‘v’ does not name a type
   64 |     for ( auto v : G[u]) {
      |                ^
answer.code:70:6: error: expected ‘;’ before ‘}’ token
   70 |     }
      |      ^
      |      ;
   71 | }
      | ~     
answer.code:71:1: error: expected primary-expression before ‘}’ token
   71 | }
      | ^
answer.code:70:6: error: expected ‘;’ before ‘}’ token
   70 |     }
      |      ^
      |      ;
   71 | }
      | ~     
answer.code:71:1: error: expected primary-expression before ‘}’ token
   71 | }
      | ^
answer.code:70:6: error: expected ‘)’ before ‘}’ token
   70 |     }
      |      ^
      |      )
   71 | }
      | ~     
answer.code:64:9: note: to match this ‘(’
   64 |     for ( auto v : G[u]) {
      |         ^
answer.code:71:1: error: expected primary-expression before ‘}’ token
   71 | }
      | ^
answer.code: In function ‘void dfs2(int, int)’:
answer.code:78:16: error: ‘v’ does not name a type
   78 |     for ( auto v : G[u])
      |                ^
answer.code:79:51: error: expected ‘;’ before ‘}’ token
   79 |         if (v != fa[u] && v != son[u]) dfs2(v, v);
      |                                                   ^
      |                                                   ;
   80 | }
      | ~                                                  
answer.code:80:1: error: expected primary-expression before ‘}’ token
   80 | }
      | ^
answer.code:79:51: error: expected ‘;’ before ‘}’ token
   79 |         if (v != fa[u] && v != son[u]) dfs2(v, v);
      |                                                   ^
      |                                                   ;
   80 | }
      | ~                                                  
answer.code:80:1: error: expected primary-expression before ‘}’ token
   80 | }
      | ^
answer.code:79:51: error: expected ‘)’ before ‘}’ token
   79 |         if (v != fa[u] && v != son[u]) dfs2(v, v);
      |                                                   ^
      |                                                   )
   80 | }
      | ~                                                  
answer.code:78:9: note: to match this ‘(’
   78 |     for ( auto v : G[u])
      |         ^
answer.code:80:1: error: expected primary-expression before ‘}’ token
   80 | }
      | ^
answer.code: In function ‘void build(const std::vector<int>&, int)’:
answer.code:112:5: error: ‘function’ was not declared in this scope
  112 |     function< void( int)> dfs = [&]( int u) {
      |     ^~~~~~~~
answer.code:112:5: note: ‘std::function’ is only available from C++11 onwards
answer.code:112:15: error: expected primary-expression before ‘void’
  112 |     function< void( int)> dfs = [&]( int u) {
      |               ^~~~
answer.code:129:5: error: ‘dfs’ was not declared in this scope; did you mean ‘ffs’?
  129 |     dfs(1);
      |     ^~~
      |     ffs
answer.code: In function ‘void Freopen()’:
answer.code:5:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    5 |     freopen("", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~
answer.code:6:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    6 |     freopen("", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~