# include <bits/stdc++.h>
using namespace std;
long long ans,dp[100005],score[100005];
vector<int> edge[100005];
void DFS(int n,int parent)
{
dp[n]=score[n];
for(int i=0;i<edge[n].size();i++)
{
if(edge[n][i]!=parent)
{
DFS(edge[n][i],n);
if(dp[edge[n][i]]>0)
dp[n]+=dp[edge[n][i]];
}
}
ans=max(ans,dp[n]);
}
int main()
{
int t;
cin>>t;
while(t--)
{
int N;
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%lld",&score[i]);
for(int i=1;i<=N;i++)
edge[i].clear();
int u,v;
for(int i=0;i<N-1;i++)
{
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
ans=score[1];
DFS(1,-1);
cout<<ans<<endl;
}
return 0;
}
IyBpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKbG9uZyBsb25nIGFucyxkcFsxMDAwMDVdLHNjb3JlWzEwMDAwNV07CnZlY3RvcjxpbnQ+IGVkZ2VbMTAwMDA1XTsKCnZvaWQgREZTKGludCBuLGludCBwYXJlbnQpCnsKICAgIGRwW25dPXNjb3JlW25dOwogICAgZm9yKGludCBpPTA7aTxlZGdlW25dLnNpemUoKTtpKyspCiAgICB7CiAgICAgICAgaWYoZWRnZVtuXVtpXSE9cGFyZW50KQogICAgICAgIHsKICAgICAgICAgICAgREZTKGVkZ2Vbbl1baV0sbik7CiAgICAgICAgICAgICAgICBpZihkcFtlZGdlW25dW2ldXT4wKQogICAgICAgICAgICAgICAgICAgIGRwW25dKz1kcFtlZGdlW25dW2ldXTsKICAgICAgICB9CiAgICB9CiAgICBhbnM9bWF4KGFucyxkcFtuXSk7Cn0KCmludCBtYWluKCkKewogICAgaW50IHQ7CiAgICBjaW4+PnQ7CiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICAgaW50IE47CiAgICAgICAgc2NhbmYoIiVkIiwmTik7CiAgICAgICAgZm9yKGludCBpPTE7aTw9TjtpKyspCiAgICAgICAgICAgIHNjYW5mKCIlbGxkIiwmc2NvcmVbaV0pOwoKICAgICAgICBmb3IoaW50IGk9MTtpPD1OO2krKykKICAgICAgICAgICAgZWRnZVtpXS5jbGVhcigpOwogICAgICAgIGludCB1LHY7CiAgICAgICAgZm9yKGludCBpPTA7aTxOLTE7aSsrKQogICAgICAgIHsKICAgICAgICAgICAgc2NhbmYoIiVkJWQiLCZ1LCZ2KTsKICAgICAgICAgICAgZWRnZVt1XS5wdXNoX2JhY2sodik7CiAgICAgICAgICAgIGVkZ2Vbdl0ucHVzaF9iYWNrKHUpOwogICAgICAgIH0KICAgICAgICBhbnM9c2NvcmVbMV07CiAgICAgICAgREZTKDEsLTEpOwogICAgICAgIGNvdXQ8PGFuczw8ZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==