/*
Tips:
1.Remember to consider the zero situation in the covering problems
2.Remember to test the special small samples
3.Binary search : which side of the interval is closed
*/

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (ll i = a; i <= ll(b); ++i)
#define REP(a) for(ll i = 0;i < a;i++)
#define REM(a,b) (((a)%(b) == 0)?(b):((a)%(b)+(b))%(b)) 

typedef long long ll;
typedef double db;
constexpr ll NAX = 1e5+10;
constexpr ll M = 0;
constexpr ll PINF = 0x3FFFFFFFFFFFFFFF;
constexpr ll NINF = -0x3FFFFFFFFFFFFFFF;

ll alst[NAX],seg[NAX<<2];
vector<ll> ed[NAX];
ll n;

inline ll ls(ll a){return a<<1;}
inline ll rs(ll a){return (a<<1)|1;}

inline void build(ll l = 0,ll r = n-1,ll p = 1){
    if(l == r){
        seg[p] = alst[l];
        return;
    }
    ll mid = (l+r)>>1;
    build(l,mid,ls(p));
    build(mid+1,r,rs(p));
    seg[p] = min(seg[ls(p)],seg[rs(p)]);
}

ll query(ll ql,ll qr,ll p = 1,ll l = 0,ll r = n-1){
    if(ql <= l && qr >= r)
        return seg[p];
    ll mid = (l+r)>>1;
    ll reg = PINF;
    if(!(qr < l || mid < ql))
        reg = min(query(ql,qr,ls(p),l,mid),reg);
    if(!(qr < mid+1 || ql > r))
        reg = min(query(ql,qr,rs(p),mid+1,r),reg);
    return reg;
}

bool vis[NAX];
ll dep[NAX],pnt[NAX][20],lg[NAX];
vector<ll> deplst[NAX];
ll maxdep = 0;

inline void dfs(ll cur){
    vis[cur] = 1;
    maxdep = max(maxdep,dep[cur]);
    deplst[dep[cur]].push_back(cur);
    FOR(i,1,19)
        pnt[cur][i] = pnt[pnt[cur][i-1]][i-1];
    for(auto tmp:ed[cur]){
        if(!vis[tmp]){
            dep[tmp] = dep[cur]+1;
            pnt[tmp][0] = cur;
            dfs(tmp);
        }
    }
}

inline ll lca(ll a,ll b){
    if(dep[a] > dep[b]) swap(a,b);
    while(dep[a] < dep[b])
        b = pnt[b][lg[dep[b]-dep[a]]];
    if(a == b) return a;
    for(ll i = 19;i >= 0;i--){
        if(pnt[a][i] != pnt[b][i])
            a = pnt[a][i],b = pnt[b][i];
    }
    return pnt[a][0];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    ll u,v,t;
    cin >> t;
    FOR(i,0,19)
        pnt[1][i] = 1;    
    FOR(i,2,NAX-1)
        lg[i] = lg[i/2]+1;  
    while(t--){
        cin >> n;
        deplst[0].clear();
        FOR(i,1,n){
            ed[i].clear();
            vis[i] = 0;
            deplst[i].clear();
            maxdep = 0;
        }
        FOR(i,0,n-1)
            cin >> alst[i];
        build();
        FOR(i,1,n-1){
            cin >> u >> v;
            ed[u].push_back(v);
            ed[v].push_back(u);
        }
        dep[1] = 0;
        dfs(1);
        ll ans = alst[0];
        FOR(k,1,maxdep){
            vector<ll> dp(deplst[k].size());
            stack<array<ll,2>> st;
            st.push({-1,-1});
            dp[0] = query(0,k);
            FOR(i,0,(int)deplst[k].size()-2){
                ll p = lca(deplst[k][i],deplst[k][i+1]);
                if(dep[p] > st.top()[0])
                    st.push({dep[p],i});
                while(dep[p] < st.top()[0]){
                    ll last = st.top()[1];
                    dp[i] = min(((last > 0?dp[last-1]:0))+query(k-st.top()[0],k),dp[i]);
                    // cout << p << ' ' << last << ' ' << ((last > 0?dp[last-1]:0))+query(k-st.top()[0],k) << endl;
                    st.pop();
                }
                if(st.size() == 1) st.push({dep[p],0});
                dp[i+1] = dp[i]+query(0,k);
            }
            while(st.size() != 1){
                ll last = st.top()[1];
                dp.back() = min(((last > 0?dp[last-1]:0))+query(k-st.top()[0],k),dp.back());
                // cout << k-st.top()[0] << ' ' << k << ' ' << query(k-st.top()[0],k) << '\n';
                st.pop();
            }
            // cout << dp.back() << ' ';
            ans += dp.back();
        }
        cout << ans << '\n';
        if(ans == 174){
            cout << n << '\n';
            FOR(i,0,n-1)
                cout << alst[i] << ' ';
        }
    }
    return 0;
}