#include<bits/stdc++.h> #define int unsigned long long usingnamespace std;
inlineintread(){ int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); } return x * f; }
constint N = 3e5 + 10, M = 20; vector<int>g[N]; int a[N], dp[N][M];
voiddfs(int u, int fa){ for(int i = 1; i < M; i++){ dp[u][i] = a[u] * i; } for(auto &v : g[u]){ if(v == fa) continue; dfs(v, u); int pos = -1, minn = 1e18; for(int j = 1; j < M; j++){ if(dp[v][j] < minn){ minn = dp[v][j]; pos = j; } } int last = 1e18; for(int j = 1; j < M; j++){ if(j == pos) continue; last = min(last, dp[v][j]); } for(int i = 1; i < M; i++){ if(i == pos) dp[u][i] += last; else dp[u][i] += minn; } } }
voidsolve(){ int n = read(); for(int i = 1; i <= n; i++) a[i] = read(), g[i].clear(); for(int i = 1; i < n; i++){ int x = read(), y = read(); g[x].emplace_back(y); g[y].emplace_back(x); } dfs(1, 0); cout << *min_element(dp[1] + 1, dp[1] + M) << '\n'; }
signedmain(){ int t = read(); while(t--) solve(); return0; }