#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define l(x) (x<<1)
#define r(x) (x<<1|1)
#define mpr make_pair
//mt19937_64 ra(time(0) ^ (*new char));
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
const int SIZE = 100005;
const int mod = 998244353;
int T, n;
int head[SIZE], ver[SIZE*2], nxt[SIZE*2], tot;
int rt[SIZE], tots;
ll a[SIZE];
int d[SIZE];

inline int rd(){
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		x = (x<<1) + (x<<3) + (ch^48);
		ch = getchar();
	}
	return x*f;
}

ll power(ll x, ll y){
	ll jl = 1;
	while(y){
		if(y & 1) jl = (jl * x) % mod;
		x = (x * x) % mod;
		y >>= 1;
	}
	return jl;
}

void add(int x, int y){
	ver[++tot] = y, nxt[tot] = head[x];
	head[x] = tot;	
}

struct Tree{
	int l, r;
	ll sum;
}t[SIZE*200];

void clear(int p){
	t[p].l = t[p].r = t[p].sum = 0;
}

void pushup(int p){
	t[p].sum = t[t[p].l].sum + t[t[p].r].sum;	
}

int merge(int &x, int y, int l, int r, int now){
	if(!y) return x;
	if(!x) x = ++tots, clear(x);
	if(l == r){
		if(l-now-1 >= 0) t[x].sum += min(t[y].sum, a[l-now-1]);
//		cout << l << " " << t[x].sum << endl;
		return x;
	}
	int mid = (l + r) >> 1;
	t[x].l = merge(t[x].l, t[y].l, l, mid, now);
	t[x].r = merge(t[x].r, t[y].r, mid+1, r, now);
	pushup(x);
	return x;
}

void ask(int p, int l, int r){
	if(!p) return;
	if(l == r){
		t[p].sum = min(t[p].sum, a[l]);
		return;
	}
	int mid = (l + r) >> 1;
	ask(t[p].l, l, mid);
	ask(t[p].r, mid+1, r);
	pushup(p);
}

void dfs(int x, int fa){
	for(int i = head[x]; i; i = nxt[i]){
		int y = ver[i];
		if(y == fa) continue;
		d[y] = d[x] + 1;
		dfs(y, x);
		rt[x] = merge(rt[x], rt[y], 0, n-1, d[x]);
	}
	change(rt[x], 0, n-1, d[x], 0);
//	cout << x << " " << t[rt[x]].sum << endl;
}

int main(){
	T = rd();
	while(T--){
		tot = tots = 0;
		for(int i = 1; i <= n; i++) head[i] = 0;
		n = rd();
		for(int i = 0; i < n; i++) a[i] = rd();
		for(int i = 1; i < n; i++){
			int x = rd(), y = rd();
			add(x, y); add(y, x);
			rt[i] = ++tots; clear(tots);
		}
		rt[n] = ++tots; clear(tots);
		dfs(1, 0);
		ask(rt[1], 0, n-1);
		printf("%lld\n", t[rt[1]].sum);
	}
	return 0;
}

/*
3
4
10 15 40 1
1 2
2 3
2 4
5
10 5 1 100 1000
1 2
2 3
2 4
4 5
4
1000 200 10 8
1 2
2 3
3 4
*/

answer.code: In function ‘void dfs(int, int)’:
answer.code:96:9: error: ‘change’ was not declared in this scope
   96 |         change(rt[x], 0, n-1, d[x], 0);
      |         ^~~~~~