#include<bits/stdc++.h>
using namespace std;
typedef array<int,4> qr; //(pre,L,R,nxt)
typedef long long ll;
const ll N = 160,INF = 1e18;
template<typename T>void tomin(T& x,T y){x = min(x,y);}
template<typename T>void tomax(T& x,T y){x = max(x,y);}
//
int T,n,a[N],dis[N][N]; ll ans;
vector<int> e[N];

int arr[N],tot;
int find(int u,int fa,int r){
    if(u==r){
        arr[++tot] = u;
        return 1;
    }
    for(auto v : e[u])if(v != fa && find(v,u,r)){
        arr[++tot] = u;
        return 1;
    }
    return 0;
}
int vis[N],cnt;
void pdfs(int u,int fa){
    for(auto v : e[u])if(v != fa && !vis[v]){
        cnt++;
        pdfs(v,u);
    }
}

map<qr,int> _R;
map<qr,ll> dp[N];

void solve(){
    cin>>n; _R.clear(); ans = 0; for(int i=0;i<=n;i++)dp[i].clear();
    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n+1;i++)e[i].clear();
    for(int i=1,u,v;i<=n;i++){
        cin>>u>>v; 
        e[u].push_back(v); e[v].push_back(u);
    }
    //预处理
    for(int x=1;x<=n+1;x++)for(int y=1;y<=n+1;y++){
        tot = 0; find(x,0,y); reverse(arr+1,arr+1+tot); dis[x][y] = tot-1;
        fill(vis+1,vis+2+n,0); for(int i=1;i<=tot;i++)vis[arr[i]] = 1;
        vector<int> ex,ey;
        for(auto z : e[x])if(!vis[z])ex.push_back(z);
        for(auto z : e[y])if(!vis[z])ey.push_back(z);
        if(ex.empty() || (x==y && ex.size() == 1))ex.push_back(0);
        if(ey.empty())ey.push_back(0);

        for(auto pre : ex)for(auto suf : ey)if(pre && pre == suf)continue;else{
            if(vis[pre] || vis[suf])continue;
            vis[pre] = vis[suf] = 1; cnt = 0;
            for(int i=1;i<=tot;i++)pdfs(arr[i],0);
            qr I = {pre,x,y,suf};
            _R[I] = cnt;
            if(x==y)dp[0][I] = 0;
            vis[pre] = vis[suf] = 0;
        }
    }
    //
    for(int i=0;i<n;i++){
        for(auto [I,w] : dp[i]){ //转移
            int x = I[1],y = I[2],pre = I[0],nxt = I[3];
            int r = _R[I] - (i - dis[x][y]);
            assert(r >= 0);
            if(r > 0){ 
                tomax(dp[i+1][I],w);
            }
            if(pre){
                int flag = 0;
                for(auto z : e[pre])if(z != x){
                    flag = 1;
                    qr nI = {z,pre,y,nxt};
                    tomax(dp[i+1][nI],w + a[i+1]);
                }
                if(!flag){
                    qr nI = {0,pre,y,nxt};
                    tomax(dp[i+1][nI],w + a[i+1]);
                }
            }
            if(nxt){
                int flag = 0;
                for(auto z : e[nxt])if(z != y){
                    flag = 1;
                    qr nI = {pre,x,nxt,z};
                    tomax(dp[i+1][nI],w + a[i+1]);
                }
                if(!flag){
                    qr nI = {pre,x,nxt,0};
                    tomax(dp[i+1][nI],w + a[i+1]);
                }
            }
        }
    }
    for(auto [I,w] : dp[n])tomax(ans,w);

    cout<<ans<<endl;
}

int main(){
    //freopen("length.in","r",stdin);
    //freopen("length.out","w",stdout);

    cin>>T;
    while(T--)solve();

    return 0;
}