#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define endl '\n'
#define pq priority_queue
using namespace std;
typedef pair<int,int> pii;
vector<int>e[400010];
int a[400010];
int dp[400010][3];//父亲，自己，儿子
void dfs(int u,int fu)
{
dp[u][1]=a[u];
int sum=0;
for(auto t:e[u])
{
if(t==fu)continue;
dfs(t,u);
dp[u][1]+=min(min(dp[t][1],dp[t][2]),dp[t][0]);
dp[u][0]+=min(dp[t][1],dp[t][2]);
sum+=min(dp[t][1],dp[t][2]);
}
dp[u][2]=1e18;
for(auto t:e[u])
{
dp[u][2]=min(dp[u][2],sum-min(dp[t][1],dp[t][2])+dp[t][1]);
}
}
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],dp[i][1]=dp[i][2]=dp[i][3]=0,e[i].clear();
for(int i=1;i<n;i++)
{
int x,y;cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1,-1);
cout<<min(dp[1][1],dp[1][2])<<endl;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--)
{
solve();
}
return 0;
}