//----------shivam_wadhwa----------//
#include <bits/stdc++.h>
#define ll long long int
#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define scll(x) scanf("%lld",&x)
#define pint(c) printf("%d",c)
#define pll(c) printf("%lld",c)
#define ps() printf(" ")
#define pn() printf("\n")
#define vi vector<int>
#define vii vector<pair<int,int> >
#define mp make_pair
#define pb push_back
//loops
#define ff(i,n,a) for(i=a;i<n;++i)
#define fb(i,n,a) for(i=n,i>=a;--i)
//constants
const int mxn=1e5+1;
const int MOD=1e9+7;
using namespace std;
vi adj[mxn];
ll sol[mxn];
int visited[mxn];
ll A[mxn];
ll DFS(int src)
{
visited[src]=1;
ll sum=A[src];
for(int i=0;i<adj[src].size();++i)
{
int v=adj[src][i];
if(!visited[v])
{
ll x=DFS(v);
if(x>0)
sum+=x;
}
}
return sol[src]=sum;
}
void init(int n)
{
for(int i=1;i<=n;++i)
{
adj[i].clear();
visited[i]=0;
}
}
int main()
{
int t=1;
sc1(t);
while(t--)
{
int n;
sc1(n);
init(n);
for(int i=1;i<=n;++i)
{
scanf("%lld",&A[i]);
}
for(int i=0;i<n-1;++i)
{
int a,b;
sc2(a,b);
adj[a].pb(b);
adj[b].pb(a);
}
DFS(1);
ll ans=LLONG_MIN;
for(int i=1;i<=n;++i)
{
ans=max(ans,sol[i]);
}
printf("%lld\n",ans);
}
return 0;
}
Ly8tLS0tLS0tLS0tc2hpdmFtX3dhZGh3YS0tLS0tLS0tLS0vLwojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBsbCBsb25nIGxvbmcgaW50CiNkZWZpbmUgc2MxKHgpIHNjYW5mKCIlZCIsJngpCiNkZWZpbmUgc2MyKHgseSkgc2NhbmYoIiVkJWQiLCZ4LCZ5KQojZGVmaW5lIHNjbGwoeCkgc2NhbmYoIiVsbGQiLCZ4KQojZGVmaW5lIHBpbnQoYykgcHJpbnRmKCIlZCIsYykKI2RlZmluZSBwbGwoYykgcHJpbnRmKCIlbGxkIixjKQojZGVmaW5lIHBzKCkgcHJpbnRmKCIgIikKI2RlZmluZSBwbigpIHByaW50ZigiXG4iKQogCiNkZWZpbmUgdmkgdmVjdG9yPGludD4KI2RlZmluZSB2aWkgdmVjdG9yPHBhaXI8aW50LGludD4gPgojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIHBiIHB1c2hfYmFjawogCi8vbG9vcHMKI2RlZmluZSBmZihpLG4sYSkgZm9yKGk9YTtpPG47KytpKQojZGVmaW5lIGZiKGksbixhKSBmb3IoaT1uLGk+PWE7LS1pKQogCi8vY29uc3RhbnRzCmNvbnN0IGludCBteG49MWU1KzE7CmNvbnN0IGludCBNT0Q9MWU5Kzc7CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnZpIGFkaltteG5dOwpsbCBzb2xbbXhuXTsKaW50IHZpc2l0ZWRbbXhuXTsKbGwgQVtteG5dOwpsbCBERlMoaW50IHNyYykKewoJdmlzaXRlZFtzcmNdPTE7CglsbCBzdW09QVtzcmNdOwoJZm9yKGludCBpPTA7aTxhZGpbc3JjXS5zaXplKCk7KytpKQoJewoJCWludCB2PWFkaltzcmNdW2ldOwoJCWlmKCF2aXNpdGVkW3ZdKQoJCXsKCQkJbGwgeD1ERlModik7CgkJCWlmKHg+MCkKCQkJCXN1bSs9eDsKCQl9Cgl9CglyZXR1cm4gc29sW3NyY109c3VtOwp9CnZvaWQgaW5pdChpbnQgbikKewoJZm9yKGludCBpPTE7aTw9bjsrK2kpCgl7CgkJYWRqW2ldLmNsZWFyKCk7CgkJdmlzaXRlZFtpXT0wOwoJfQp9CmludCBtYWluKCkKewoJaW50IHQ9MTsKCXNjMSh0KTsKCXdoaWxlKHQtLSkKCXsKCQlpbnQgbjsKCQlzYzEobik7CgkJaW5pdChuKTsKCQlmb3IoaW50IGk9MTtpPD1uOysraSkKCQl7CgkJCXNjYW5mKCIlbGxkIiwmQVtpXSk7CgkJfQoJCWZvcihpbnQgaT0wO2k8bi0xOysraSkKCQl7CgkJCWludCBhLGI7CgkJCXNjMihhLGIpOwoJCQlhZGpbYV0ucGIoYik7CgkJCWFkaltiXS5wYihhKTsKCQl9CgkJREZTKDEpOwoJCWxsIGFucz1MTE9OR19NSU47CgkJZm9yKGludCBpPTE7aTw9bjsrK2kpCgkJewoJCQlhbnM9bWF4KGFucyxzb2xbaV0pOwoJCX0JCQoJCXByaW50ZigiJWxsZFxuIixhbnMpOwoJfQoJcmV0dXJuIDA7Cn0g