7.20日

#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;
}