#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

vector<int> S_, par_, group_, dep_;
vector<cat> val_up_, val_down_, sum_;

void DFS(int R, auto & G, auto & par, auto & S, auto & comp, auto & bl) {
	comp.push_back(R);
	S[R] = 1;
	ALL_THE(G[R], it) if(!bl[*it] && *it != par[R]) {
		par[*it] = R;
		DFS(*it, G, par, S, comp, bl);
		S[R] += S[*it];
	}
}

void solve(int R, auto & G, vector<cat> & V, vector<bool> & bl, cat & ret) {
	vector<int> comp;
	par_[R] = R;
	DFS(R, G, par_, S_, comp, bl);
	int sz = comp.size();
	ALL_THE(comp, it) {
		if(2*S_[*it] < sz) continue;
		bool found = true;
		ALL_THE(G[*it], jt) if(S_[*jt] < S_[*it] && 2*S_[*jt] > sz) {
			found = false;
			break;
		}
		if(found) {
			R = *it;
			break;
		}
	}
	comp.clear();
	par_[R] = R;
	DFS(R, G, par_, S_, comp, bl);

	dep_[R] = val_down_[R] = val_up_[R] = sum_[R] = 0;
	for(int i = 1; i < sz; i++) {
		group_[comp[i]] = (par_[comp[i]] == R) ? comp[i] : group_[par_[comp[i]]];
		dep_[comp[i]] = dep_[par_[comp[i]]] + 1;
		sum_[comp[i]] = sum_[par_[comp[i]]] + V[comp[i]];
		val_down_[comp[i]] = val_down_[par_[comp[i]]] + dep_[comp[i]] * V[comp[i]];
		val_up_[comp[i]] = val_up_[par_[comp[i]]] + sum_[comp[i]];
	}

	ret = max(ret, V[R]);
	for(int i = 1; i < sz; i++) {
		int v = comp[i];
		ret = max(ret, val_down_[v] + V[R] + sum_[v]);
		ret = max(ret, val_up_[v] + V[R] * (dep_[v]+1));
	}
	int mxdep = 0;
	vector<cat> sum(sz-1), val_up(sz-1), val_down(sz-1);
	vector<int> dep(sz-1), group(sz-1);
	for(int i = 1; i < sz; i++) group[i-1] = group_[comp[i]];
	for(int i = 1; i < sz; i++) {
		dep[i-1] = dep_[comp[i]];
		mxdep = max(mxdep, dep[i-1]);
	}
	for(int i = 1; i < sz; i++) sum[i-1] = sum_[comp[i]];
	for(int i = 1; i < sz; i++) val_down[i-1] = val_down_[comp[i]];
	for(int i = 1; i < sz; i++) val_up[i-1] = val_up_[comp[i]];
	sz--;

	for(int k = 0; k < 2; k++) {
		int last_group = -1;
		vector<bool> live(mxdep+2, false);
		vector<int> prev(mxdep+2, 0), nxt(mxdep+2, 0);
		vector<cat> val(mxdep+2, -OVER9000);
		set<int> live_lst;
		map<cat, pair<int, int> > vx; // vertices
		live_lst.insert(0);
		for(int i = 0; i < sz; i++) {
			if(group[i] != last_group) {
				for(int j = i-1; j >= 0; j--) {
					if(group[j] != last_group) break;
					// add val_up[j], dep[j]+1
					int d = dep[j]+1;
					if(!live[d]) {
						auto it = live_lst.lower_bound(d);
						it--;
						int p = *it, n = nxt[*it];
						if(p == 0) {
							it++;
							if(it == end(live_lst)) {
								prev[d] = nxt[d] = 0;
								live[d] = true;
								val[d] = val_up[j];
								live_lst.insert(d);
								continue;
							}
							n = *it;
						}
						if(p != 0 && n != 0) {
							// x = intersection of val[p]+p*x, val[n]+n*x
							// max. x: val[p]+p*x >= val[n]+n*x
							cat x = (val[p]-val[n]) / (n-p);
							if(val[p]+x*p >= val_up[j]+x*d)
								if(val[n]+(x+1)*n >= val_up[j]+(x+1)*d)
									continue;
							vx.erase(x);
						}
						live[d] = true;
						val[d] = -OVER9000;
						prev[d] = p, nxt[d] = n;
						if(p != 0) nxt[p] = d;
						if(n != 0) prev[n] = d;
						live_lst.insert(d);
						val[d] = val_up[j];
					}
					else if(val[d] < val_up[j]) {
						int p = prev[d], n = nxt[d];
						if(p != 0) {
							cat x = (val[p]-val[d]) / (d-p);
							vx.erase(x);
						}
						if(n != 0) {
							cat x = (val[d]-val[n]) / (n-d);
							vx.erase(x);
						}
						val[d] = val_up[j];
					}
					else continue;
					// update
					int p = prev[d], n = nxt[d];
					while(p != 0 && prev[p] != 0) {
						cat x = (val[prev[p]]-val[p]) / (p-prev[p]);
						cat x_nw = (val[p]-val[d]) / (d-p);
						if(x_nw > x) break;
						vx.erase(x);
						live_lst.erase(p);
						live[p] = false;
						int pp = prev[p];
						prev[d] = pp;
						nxt[pp] = d;
						p = pp;
					}
					while(n != 0 && nxt[n] != 0) {
						cat x = (val[n]-val[nxt[n]]) / (nxt[n]-n);
						cat x_nw = (val[d]-val[n]) / (n-d);
						if(x_nw < x) break;
						vx.erase(x);
						live_lst.erase(n);
						live[n] = false;
						int nn = nxt[n];
						nxt[d] = nn;
						prev[nn] = d;
						n = nn;
					}
					if(p != 0) {
						cat x = (val[p]-val[d]) / (d-p);
						vx[x] = make_pair(p, d);
					}
					if(n != 0) {
						cat x = (val[d]-val[n]) / (n-d);
						vx[x] = make_pair(d, n);
					}
				}
				last_group = group[i];
			}
			if(live_lst.empty()) continue;
			auto it = vx.lower_bound(V[R]+sum[i]);
			if(it == end(vx)) {
				int id = *(live_lst.rbegin());
				ret = max(ret, val[id] + id * (V[R]+sum[i]) + val_down[i]);
			}
			else {
				int id = (it->ss).ff;
				ret = max(ret, val[id] + id * (V[R]+sum[i]) + val_down[i]);
			}
			// for(int id = 0; id <= mxdep+1; id++)
			// 	ret = max(ret, val[id] + id * (V[R]+sum[i]) + val_down[i]);
		}
		if(k == 1) break;
		reverse(begin(sum), end(sum));
		reverse(begin(val_up), end(val_up));
		reverse(begin(val_down), end(val_down));
		reverse(begin(dep), end(dep));
		reverse(begin(group), end(group));
	}

	bl[R] = true;
	ALL_THE(G[R], it) if(!bl[*it]) solve(*it, G, V, bl, ret);
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int T;
	cin >> T;
	while(T--) {
		int N;
		cin >> N;
		vector<cat> V(N);
		for(int i = 0; i < N; i++) cin >> V[i];
		vector< vector<int> > G(N);
		for(int i = 0; i < N-1; i++) {
			int u, v;
			cin >> u >> v;
			G[--u].push_back(--v);
			G[v].push_back(u);
		}
		vector<bool> bl(N, false);
		S_.resize(N);
		par_.resize(N);
		group_.resize(N);
		dep_.resize(N);
		val_up_.resize(N);
		val_down_.resize(N);
		sum_.resize(N);
		cat ret = -OVER9000;
		solve(0, G, V, bl, ret);
		cout << ret << "\n";
	}
	return 0;}

// look at my code
// my code is amazing