#include <bits/stdc++.h>
using namespace std;
struct Edge
{
	int to, nxt;
} e[2000010];
int ecnt = 0, head[1000010];
inline void addedge(int from, int to)
{
	e[ecnt].to = to;
	e[ecnt].nxt = head[from];
	head[from] = ecnt++;
}
int a[1000010], dep[1000010], r[1000010], l[1000010], ans = 0;
inline void dfs(int u, int fa)
{
	r[u] = dep[u] - a[u], l[u] = dep[u] + a[u];
	int mnr = INT_MAX >> 2, smnr = INT_MAX >> 2, mnl = INT_MAX >> 2, smnl = INT_MAX >> 2;
	for(int i = head[u]; i != -1; i = e[i].nxt)
	{
		int v = e[i].to;
		if(v == fa)
			continue;
		dep[v] = dep[u] + 1;
		dfs(v, u);
		r[u] = min(r[u], r[v]), l[u] = min(l[u], l[v]);
		if(r[v] < mnr)
			smnr = mnr, mnr = r[v];
		else if(r[v] < smnr)
			smnr = r[v];
		if(l[v] < mnl)
			smnl = mnl, mnl = l[v];
		else if(l[v] < smnl)
			smnl = l[v];
	}
	int res = INT_MAX;
	for(int i = head[u]; i != -1; i = e[i].nxt)
	{
		int v = e[i].to;
		if(v == fa)
			continue;
		int m = (l[v] == mnl ? smnl : mnl);
		res = min(res, r[v] + m);
		res = min(res, r[v] + dep[u] + a[u]);
		res = min(res, l[v] + dep[u] - a[u]);
	}
	ans = min(ans, res - dep[u] * 2 + 1);
}
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int n;
		scanf("%d", &n);
		for(int i = 1; i <= n; i++)
			head[i] = -1;
		ecnt = 0;
		for(int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		for(int i = 1; i < n; i++)
		{
			int u, v;
			scanf("%d %d", &u, &v);
			addedge(u, v), addedge(v, u);
		}
		ans = 1;
		dep[1] = 1;
		dfs(1, 1);
		printf("%d\n", ans);
	}
	return 0;
}