#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
#define popcnt __builtin_popcountll
const ll mod = 998244353;
inline ll read(){
	ll 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*10+ch-'0', ch=getchar();
	return x*f;
}
inline int lg2(int x){ return 31^__builtin_clz(x); }
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline void addmod(int &x){ if(x >= mod) x -= mod; }
inline void addmod(ll &x){ if(x >= mod) x -= mod; }
inline ll qpow(ll a,ll b){
	ll ans=1, base=a;
	while(b){
		if(b&1) ans=ans*base%mod;
		base=base*base%mod; b>>=1;
	}
	return ans;
}
const ll INF = 1e18;
inline ll INV(ll x){ return qpow(x, mod-2); };
ll n,sz[155],a[155],d[155][155],f[155][155][155][2][2],p[155][155];
vector<ll>E[155];

void dfs(ll x,ll fa){
	sz[x]=0;
	for(auto y: E[x]){
		if(y==fa) continue;
		dfs(y, x);
		sz[x]+=sz[y]+1;
	}
}
int calc(int x,int y){
	int ret;
	if(sz[x]<sz[y]) ret = sz[x]+1;
	else ret = n-1-sz[y];
	// cout<<x<<" from "<<y<<" ret = "<<ret<<endl;
	return ret;
}
void chkmax(ll &a,ll b){ a=max(a,b); }
void chkmin(ll &a,ll b){ a=min(a,b); }
void procedure(){
	n=read()+1;
	for(ll i=1;i<n;i++) a[i]=read();
	if(n == 2){
		printf("%lld\n", a[1]);
		return;
	}
	for(ll i=0;i<=n+1;i++)for(ll j=0;j<=n+1;j++)
		d[i][j]=(i!=j)*INF;
	for(ll i=0;i<=n+1;i++)for(ll j=0;j<=n+1;j++)
		for(ll k=0;k<=n+1;k++)
		for(auto s:{0,1}) for(auto t:{0,1}) f[i][j][k][s][t]=-INF;
	for(ll i=1;i<n;i++){
		ll u=read(), v=read();
		E[u].pb(v); E[v].pb(u);
		d[u][v]=d[v][u]=1;
	}	
	dfs(1, 0);
	for(ll k=1;k<=n;k++)
		for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++)
		d[i][j]=min(d[i][k]+d[k][j], d[i][j]);
	vector<tuple<ll,ll,ll>>q;
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=n;j++){
			if(d[i][j] >= 2){
				p[i][j]=n-1;
				for(auto x: E[i])
					if(1+d[x][j]==d[i][j]) p[i][j]-=calc(i,x);
				for(auto y: E[j])
					if(1+d[y][i]==d[i][j]) p[i][j]-=calc(j,y);

				q.pb(d[i][j], i, j);
				if(d[i][j]==2) {
					f[1][i][j][0][0]=0;
					// cout<<"here "<<1<<" "<<i<<" "<<j<<" 0 0 "<<endl;
					// cout<<"p = "<<p[i][j]<<endl;
				}
			} 
		}
	sort(q.begin(), q.end());
	ll ans = -INF;
	for(ll i=1;i<=n;i++){
		for(auto [D,x,y]: q){
			// cout<<"find "<<x<<", "<<y<<endl;
			for(auto s: {0, 1}) for(auto t: {0, 1}){
				ll lim=p[x][y]+s+t;
				if(i-1>lim) continue;
				if(i==n) {chkmax(ans, f[i][x][y][s][t]); continue;}
				if(f[i][x][y][s][t] < 1e9){
					// cout<<"turn "<<i<<" node=("<<x<<","<<y<<") s="<<s<<" t="<<t<<" val="<<f[i][x][y][s][t]<<endl;
				}
				chkmax(f[i+1][x][y][s][t], f[i][x][y][s][t]);
				ll val = f[i][x][y][s][t]+a[i];
				if(!s){ // choose left
					bool flg = 0;
					for(auto z: E[x])
						if(d[z][y]==D+1){
							flg = 1;
							chkmax(f[i+1][z][y][s][t], val);
						}
					if(!flg)
						chkmax(f[i+1][x][y][1][t], val);
				}
				if(!t){
					bool flg = 0;
					for(auto z: E[y])
						if(d[z][x]==D+1){
							flg = 1;
							chkmax(f[i+1][x][z][s][t], val);
						}
					if(!flg)
						chkmax(f[i+1][x][y][s][1], val);
				}
			}
		}
	}
	printf("%lld\n", ans);
}
int main(){
	#ifdef LOCAL
		assert(freopen("input.txt","r",stdin));
		assert(freopen("output.txt","w",stdout));
	#endif
	ll T=read();
	// math_init();
	// NTT::init();
	while(T--) procedure();
	return 0;
}