/*
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(l > qr || r < ql)
return PINF;
if(ql <= l && qr >= r)
return seg[p];
ll mid = (l+r)>>1;
ll reg = PINF;
if(!(r < ql || l > mid))
reg = min(query(ql,qr,ls(p),l,mid),reg);
if(!(r < mid+1 || l > ql))
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(),0);
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';
}
return 0;
}