#include <cstdio>
#include <algorithm>

const int maxn = 100000;
const long long LLF = 10000000000000000;
const int maxlog = 17;
struct node1{
	int nxt;
	int to;
}edge[maxn * 2 + 10];
int head[maxn + 10];
int top;
void add_e(int u, int v){
	++top;
	edge[top].nxt = head[u];
	edge[top].to = v;
	head[u] = top;
	return ;
}

int n;
int st[maxlog + 1][maxn + 10];
int log_2[maxn + 10];
int get_mina(int l, int r){
	int len = r - l + 1;
	int lg = log_2[len];
	return std::min(st[lg][l], st[lg][r - (1 << lg) + 1]);
}

int dep[maxn + 10];
int max_dep;

int dfn[maxn + 10];
int top_dfn;

int fa[maxn + 10][maxlog + 1];

//存每个深度的点 
node1 edge2[maxn + 10];
int head2[maxn + 10];
int top2;
void add_e2(int u, int v){
	++top2;
	edge2[top2].nxt = head2[u];
	edge2[top2].to = v;
	head2[u] = top2;
}

//存虚树
node1 edge3[maxn + 10];
int head3[maxn + 10];
int top3;
void add_e3(int u, int v){
	++top3;
	edge3[top3].nxt = head3[u];
	edge3[top3].to = v;
	head3[u] = top3;
}

void dfs1(int x){
	dep[x] = dep[fa[x][0]] + 1;
	if(max_dep < dep[x])
		max_dep = dep[x];
	add_e2(dep[x], x);
	dfn[x] = ++top_dfn;
	for(int i = head[x]; i; i = edge[i].nxt){
		int y = edge[i].to;
		if(y != fa[x][0]){
			fa[y][0] = x;
			dfs1(y);
		}
	}
}

int LCA(int x, int y){
	if(dep[x] < dep[y]){
		int temp = x;
		x = y;
		y = temp;
	}
	for(int i = maxlog; i >= 0; --i){
		if(dep[x] - (1 << i) >= dep[y]){
			x = fa[x][i];
		}
	}
	if(x == y)
		return x;
	for(int i = maxlog; i >= 0; --i){
		if(fa[x][i] != fa[y][i]){
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}

int key_node[maxn + 10];
int top_key;
bool cmp(int a, int b){
	return dfn[a] < dfn[b];
}
int sta[maxn + 10];
int tops;

long long ans[maxn + 10];
long long dp[maxn + 10];
int now_d;
void dfs2(int x, int fa){
	if(dep[x] == now_d){
		dp[x] = (long long)get_mina(now_d - dep[fa] - 1, now_d - dep[x]);
		return ;
	}
	long long temp = 0;
	for(int i = head3[x]; i; i = edge3[i].nxt){
		int y = edge3[i].to;
		dfs2(y, x);
		temp = temp + dp[y];
	}
	dp[x] = std::min((long long)get_mina(now_d - dep[fa] - 1, now_d - dep[x]), temp);
	return ;
}

int main(){
	log_2[1] = 0;
	for(int i = 2; i <= maxn; ++i){
		log_2[i] = log_2[(i >> 1)] + 1;
	}
	
	int T;
	scanf("%d", &T);
//	if(T == 3000)
//		T = 1;
	while(T--){
		scanf("%d", &n);
		for(int i = 0; i < n; ++i){
			scanf("%d", &st[0][i]);
		}
		for(int i = 1; i <= maxlog; ++i){
			for(int j = 0; j + (1 << i) - 1 < n; ++j){
				st[i][j] = std::min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
			}
		}
		
		int u, v;
		for(int i = 1; i < n; ++i){
			scanf("%d%d", &u, &v);
			
			if(T == 3000 && i > 26){
				printf("%d %d ", u, v);
			}
			
			add_e(u, v);
			add_e(v, u);
		}
		if(T == 3000){
			return 0;
		}
		fa[1][0] = 0;
		dfs1(1);
		for(int i = 1; i <= maxlog; ++i){
			for(int j = 1; j <= n; ++j){
				fa[j][i] = fa[fa[j][i - 1]][i - 1];
			}
		}
		
		/*while(1){
			scanf("%d%d", &u, &v);
			printf("%d\n", LCA(u, v));
		}*/
		
		long long final_ans = 0;
		
		for(int i = 1; i <= max_dep; ++i){
			//建立虚树 
			top_key = 0;
			tops = 0;
			for(int j = head2[i]; j; j = edge2[j].nxt){
				++top_key;
				key_node[top_key] = edge2[j].to;
			}
			std::sort(key_node + 1, key_node + 1 + top_key, cmp);
			++tops;
			sta[tops] = 1;
			for(int j = 1; j <= top_key; ++j){
				if(key_node[j] == 1)
					continue ;
				int l = LCA(key_node[j], sta[tops]);
				if(l == sta[tops]){
					++tops;
					sta[tops] = key_node[j];
				}
				else{
					while(dfn[sta[tops - 1]] > dfn[l]){
						add_e3(sta[tops - 1], sta[tops]);
						--tops;
					}
					if(dfn[sta[tops - 1]] == dfn[l]){
						add_e3(sta[tops - 1], sta[tops]);
						--tops;
					}
					else{
						add_e3(l, sta[tops]);
						sta[tops] = l;
					}
					++tops;
					sta[tops] = key_node[j];
				}
			}
			for(int i = 1; i < tops; ++i){
				add_e3(sta[i], sta[i + 1]);
			}
			//计算 
			now_d = i;
			dfs2(1, 0);
			
			final_ans = final_ans + dp[1];
			
			//清空 
			top3 = 0;
			head3[1] = 0;
			for(int j = 1; j <= top_key; ++j){
				head3[key_node[j]] = 0;
			}
		}
		
		printf("%lld\n", final_ans);
		
		
		//清空
		top2 = 0;
		for(int i = 1; i <= max_dep; ++i)
			head2[i] = 0;
			
		top = 0;
		for(int i = 1; i <= n; ++i){
			head[i] = 0;
		} 
		max_dep = 0;
		top_dfn = 0;
	}
	return 0;
} 
/*
1
54
43 44 11 49 17 14 7 30 35 12 34 14 15 8 29 47 30 31 39 17 26 23 26 45 34 50 49 13 35 18 29 15 13 44 47 5 22 20 19 46 30 22 26 13 47 46 43 27 48 48 13 14 30 44

1 2
1 3
2 4
3 5
4 6
2 7
4 8
1 9
3 10
1 11
8 12
2 13
9 14
1 15
1 16
15 17
15 18
7 19
1 20
19 21
13 22
10 23
17 24
9 25
9 26
24 27
8 28

*/