#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define gt getchar
#define pt putchar
#define fst first
#define scd second
#define SZ(s) ((int)s.size())
#define all(s) s.begin(),s.end()
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
const int N=155;
using namespace std;
using namespace __gnu_pbds;
typedef pair<int,int> pii;
template<class T,class I> inline void chkmax(T &a,I b){a=max(a,(T)b);}
template<class T,class I> inline void chkmin(T &a,I b){a=min(a,(T)b);}
inline bool __(char ch){return ch>=48&&ch<=57;}
template<class T> inline void read(T &x){
	x=0;bool sgn=0;static char ch=gt();
	while(!__(ch)&&ch!=EOF) sgn|=(ch=='-'),ch=gt();
	while(__(ch)) x=(x<<1)+(x<<3)+(ch&15),ch=gt();
	if(sgn) x=-x;
}
template<class T,class ...I> inline void read(T &x,I &...x1){
	read(x);
	read(x1...);
}
template<class T> inline void print(T x){
	static char stk[70];short top=0;
	if(x<0) pt('-');
	do{stk[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
	while(top) pt(stk[top--]);
}
template<class T> inline void printsp(T x){
	print(x);
	putchar(' ');
}
template<class T> inline void println(T x){
	print(x);
	putchar('\n');
}
int T,n,a[N];
struct Edge{
	int to,nxt;
}e[N<<1];
int head[N],cnt,deg[N];
inline void add_edge(int f,int t){
	e[++cnt].to=t;
	e[cnt].nxt=head[f];
	head[f]=cnt;
}
inline void add_double(int f,int t){
	add_edge(f,t);
	add_edge(t,f);
	deg[f]++,deg[t]++;
}
int dep[N][N],siz[N][N],fa[N][N];
void dfs(int u,int fa,int rt){
	siz[rt][u]=1,::fa[rt][u]=fa;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		dep[rt][v]=dep[rt][u]+1;
		dfs(v,u,rt);
		siz[rt][u]+=siz[rt][v];
	}
} 
ll f[N][N][N][2][2];
inline void clear(){
	cnt=0;
	for(int i=1;i<=n+1;++i) head[i]=deg[i]=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n+1;++j){
			for(int k=1;k<=n+1;++k){
				for(int p=0;p<2;++p){
					for(int q=0;q<2;++q){
						f[i][j][k][p][q]=-1;
					}
				}
			}
		}
	}
} 
ll dfs(int k,int u,int v,bool p,bool q){
	if(u>v) swap(u,v),swap(p,q);
	ll &ans=f[k][u][v][p][q];
	if(~ans) return ans;
	if(k<dep[u][v]||k>n-p*(siz[fa[v][u]][u]-1)-q*(siz[fa[u][v]][v]-1)) return ans=-1e18;
	if(!dep[u][v]) return ans=0;
	ans=-1e18;  
	chkmax(ans,dfs(k-1,fa[v][u],v,0,q)+a[k]);
	chkmax(ans,dfs(k-1,u,fa[u][v],p,0)+a[k]); 
	chkmax(ans,dfs(k-1,u,v,p,q));
	return ans;
}
inline void solve(){
	read(n);
	clear();
	for(int i=1;i<=n;++i) read(a[i]);
	for(int u,v,i=1;i<=n;++i){
		read(u,v);
		add_double(u,v);
	}
	for(int i=1;i<=n+1;++i) dep[i][i]=0,dfs(i,0,i);
//	return println(dfs(5,2,6,1,1));
	ll ans=0;
	for(int i=1;i<=n+1;++i){
		if(deg[i]!=1) continue;
		for(int j=1;j<=n+1;++j){
			if(deg[j]!=1) continue;
			chkmax(ans,dfs(n,i,j,1,1));
		}
	}
	println(ans);
}
signed main(){
	read(T);
	while(T--) solve();
	return 0;
}
/*
1
5
1 7 3 5 4
1 3
2 3
3 4
4 5
4 6
*/