TREEVERS

#include<bits/stdc++.h>

using namespace std;

const int MX = (1<<20);

int T , n;

int col[MX] , cnt[MX][2] , sz[MX];

vector < int > v[MX];

long long dp[MX];

bool cmp(pair < int , int > A , pair < int , int > B){
    return 1ll * B.first * A.second < 1ll * A.first * B.second;
}
void dfs(int x , int p){

    dp[x] = 0;
    sz[x] = 1;

    cnt[x][0] = cnt[x][1] = 0;

    cnt[x][col[x]]++;

    vector < pair < int , int > > vec;

    for(auto nxt : v[x]){
        if(nxt == p) continue;
        dfs(nxt , x);
        cnt[x][0] += cnt[nxt][0];
        cnt[x][1]+= cnt[nxt][1];
        vec.push_back({cnt[nxt][0] , cnt[nxt][1]});
        dp[x] += dp[nxt];
        sz[x] += sz[nxt];
    }

    sort(vec.begin() , vec.end() , cmp);

    int cur = col[x];

    for(auto pp : vec){
        dp[x] += 1ll * pp.first * cur;
        cur += pp.second;
    }
}
int main(){
    cin>>T;
    int alln = 0;
    while(T--){
        cin>>n;
        alln += n;
        for(int j = 1 ; j <= n ; j++){
            v[j].clear();
        }
        for(int j = 1 ; j <= n ; j++)
            cin>>col[j];
        for(int j = 1 ; j < n ; j++){
            int a , b;
            cin>>a>>b;
            assert(a != b);
            v[a].push_back(b);
            v[b].push_back(a);
        }
        dfs(1 , -1);
        assert(sz[1] == n);
        cout<<dp[1]<<endl;

    }

}