#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int> e[N];
int deg[N],a[N],n,col[N],eu[N],ev[N];
bool vis[N];
long long sum[3];
void init()
{
    for(int i=1;i<=n;++i) e[i].clear(),deg[i]=col[i]=vis[i]=0;
    memset(sum,0,sizeof(sum));
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        for(int i=4;i<=n;++i)
        {
            scanf("%d%d",&eu[i],&ev[i]);
            deg[i]+=(eu[i]>3),deg[i]+=(ev[i]>3);
            e[eu[i]].push_back(i),e[ev[i]].push_back(i);
            e[i].push_back(eu[i]),e[i].push_back(ev[i]);
        }
        queue<int> q;
        vis[1]=vis[2]=vis[3]=true;
        col[2]=1,col[3]=2;
        for(int i=4;i<=n;++i) if(!deg[i])
        {
            q.push(i);
            col[i]=3-col[eu[i]]-col[ev[i]];
            vis[i]=true;
        }
        while(!q.empty())
        {
            int u=q.front(); q.pop();
            for(auto v:e[u]) if(!vis[v])
            {
                if(!(--deg[v]))
                {
                    col[v]=3-col[eu[v]]-col[ev[v]];
                    vis[v]=true, q.push(v);
                }
            }
        }
        for(int i=1;i<=n;++i) sum[col[i]]+=a[i];
        printf("%lld\n",max(sum[0],max(sum[1],sum[2])));
    }
}