#include<cstdio>
#include<iostream>
#include<map>

using namespace std;

typedef long long LL;

const int maxn = 1e6+5; 

int n;
int a[maxn];

map<int,int> num[maxn]; 

struct edgeType
{
	int u,v;
	edgeType(){}
	edgeType(int _u,int _v):u(_u),v(_v){}
}edge[maxn];
int cntEdge; 

int hp[maxn];
int he[maxn];
struct OppositeType
{
	int to,nxt;
	void add_connect(int u,int v,int x,int *head)
	{
		to=v;
		nxt=head[u];
		head[u]=x;
	}
}pt[maxn],eg[maxn];
int cntConnect;

void standing_by()
{
	int i;
	int u,v,w;
	
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	for(i=1;i<=3*n-6;i++) hp[i]=he[i]=-1;
	
	edge[1]=edgeType(2,3);
	edge[2]=edgeType(1,3);
	edge[3]=edgeType(1,2);
	
	pt[1].add_connect(1,1,1,hp);
	pt[2].add_connect(2,2,2,hp);
	pt[3].add_connect(3,3,3,hp);
	
	eg[1].add_connect(1,1,1,he);
	eg[2].add_connect(2,2,2,he);
	eg[3].add_connect(3,3,3,he);
	
	num[2][3]=num[3][2]=1;
	num[1][3]=num[3][1]=2;
	num[1][2]=num[2][1]=3;
	
	cntEdge=3;
	cntConnect=3;
	for(i=4;i<=n;i++)
	{
		scanf("%d%d",&u,&v);
		w=num[u][v];
		
		edge[cntEdge+1]=edgeType(u,i);
		edge[cntEdge+2]=edgeType(i,v);
		num[u][i]=num[i][u]=cntEdge+1;
		num[v][i]=num[i][v]=cntEdge+2;
		
		
		pt[cntConnect+1].add_connect(w,i,cntConnect+1,hp);
		eg[cntConnect+1].add_connect(i,w,cntConnect+1,he);
		
		pt[cntConnect+2].add_connect(cntEdge+1,v,cntConnect+2,hp);
		eg[cntConnect+2].add_connect(v,cntEdge+1,cntConnect+2,he);
		
		pt[cntConnect+3].add_connect(cntEdge+2,u,cntConnect+3,hp);
		eg[cntConnect+3].add_connect(u,cntEdge+2,cntConnect+3,he);
		cntEdge+=2;
		cntConnect+=3;
	}
}

bool fp[maxn];
bool fe[maxn];

LL cur;

void dfs(int x,bool isPoint)
{
	int i;
	
	if (isPoint)
	{
		fp[x]=true;
		cur+=a[x];
		for(i=he[x];~i;i=eg[i].nxt)
		{
			if (fe[eg[i].to]) continue;
			dfs(eg[i].to,false);
		}
	}else {
		fe[x]=true;
		for(i=hp[x];~i;i=pt[i].nxt)
		{
			if (fp[pt[i].to]) continue;
			dfs(pt[i].to,true);
		}
	}
}

void complete()
{
	int i;
	LL ans;
	for(i=1;i<=n;i++) fp[i]=false;
	for(i=1;i<=cntEdge;i++) fe[i]=false;
	cur=0;
	dfs(1,true);
	ans=cur;
	
	for(i=1;i<=n;i++) fp[i]=false;
	for(i=1;i<=cntEdge;i++) fe[i]=false;
	cur=0;
	dfs(2,true);
	ans=max(ans,cur);
	
	for(i=1;i<=n;i++) fp[i]=false;
	for(i=1;i<=cntEdge;i++) fe[i]=false;
	cur=0;
	dfs(3,true);
	ans=max(ans,cur);
	
	printf("%lld\n",ans);
	
	for(i=1;i<=n;i++) num[i].clear();
}

int main()
{
	int t;
	scanf("%d",&t);
	for(;t;t--)
	{
		standing_by();
		complete();
	}
	return 0;
}