#include <bits/stdc++.h>
#define inf 1234567890123456789LL
using namespace std;

using cat = long long;

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;
	for(auto v : G[R]) if(!bl[v] && v != par[R]) {
		par[v] = R;
		DFS(v, G, par, S, comp, bl);
		S[R] += S[v];
	}
}

cat solve(int R, auto & G, vector<cat> & V, vector<bool> & bl) {
	// find centroid
	vector<int> comp;
	par_[R] = R;
	DFS(R, G, par_, S_, comp, bl);
	int sz = comp.size();
	for(auto r : comp) {
		if(2*S_[r] < sz) continue;
		bool found = true;
		for(auto v : G[r]) if(S_[v] < S_[r] && 2*S_[v] > sz) {
			found = false;
			break;
		}
		if(found) {
			R = r;
			break;
		}
	}
	comp.clear();
	par_[R] = R;
	DFS(R, G, par_, S_, comp, bl);

	// precompute information for paths from the centroid
	dep_[R] = val_down_[R] = val_up_[R] = sum_[R] = 0;
	for(int i = 1; i < sz; i++) {
		int v = comp[i];
		group_[v] = (par_[v] == R) ? v : group_[par_[v]];
		dep_[v] = dep_[par_[v]] + 1;
		sum_[v] = sum_[par_[v]] + V[v];
		val_down_[v] = val_down_[par_[v]] + dep_[v] * V[v];
		val_up_[v] = val_up_[par_[v]] + sum_[v];
	}

	cat 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]];
		dep[i-1] = dep_[comp[i]];
		mxdep = max(mxdep, dep[i-1]);
		sum[i-1] = sum_[comp[i]];
		val_down[i-1] = val_down_[comp[i]];
		val_up[i-1] = val_up_[comp[i]];
	}
	sz--;

	// main part of the solution
	// maximum value of path through the centroid
	// dynamic convex hull containing up-paths
	for(int k = 0; k < 2; k++) { // up-path to the left/right of down-path
		int last_group = -1;
		// convex hull as linked list
		vector<bool> live(mxdep+2, false);
		vector<int> prev(mxdep+2, 0), nxt(mxdep+2, 0);
		vector<cat> val(mxdep+2, -inf);
		set<int> live_lst;
		map<cat, pair<int, int> > vx; // vertices of convex hull
		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 to the convex hull
					int d = dep[j]+1;
					if(!live[d]) { // add to linked list
						auto it = --live_lst.lower_bound(d);
						int p = *it, n = nxt[*it];
						if(p == 0) {
							it++;
							if(it == end(live_lst)) { // first line
								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);
							// handle lowest vertex below this new line
							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;
						live_lst.insert(d);
						val[d] = -inf;
						prev[d] = p, nxt[d] = n;
						if(p != 0) nxt[p] = d;
						if(n != 0) prev[n] = d;
						val[d] = val_up[j];
					}
					else if(val[d] < val_up[j]) { // update linked list
						int p = prev[d], n = nxt[d];
						if(p != 0) vx.erase((val[p]-val[d]) / (d-p));
						if(n != 0) vx.erase((val[d]-val[n]) / (n-d));
						val[d] = val_up[j];
					}
					else continue; // new line is not better than existing
					int p = prev[d], n = nxt[d];
					// clear up vertices below this new line
					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];
						nxt[pp] = d;
						p = prev[d] = 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];
						prev[nn] = d;
						n = nxt[d] = nn;
					}
					// add new vertices to convex hull
					if(p != 0) vx[(val[p]-val[d]) / (d-p)] = make_pair(p, d);
					if(n != 0) vx[(val[d]-val[n]) / (n-d)] = make_pair(d, n);
				}
				last_group = group[i];
			}
			if((int)live_lst.size() == 1) continue; // no lines in convex hull
			// get max. up-path and value for this down-path
			auto it = vx.lower_bound(V[R]+sum[i]);
			int id = (it == end(vx)) ? *(live_lst.rbegin()) : (it->second).first;
			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));
	}

	// recurse into subtrees of the centroid
	bl[R] = true;
	for(auto v : G[R]) if(!bl[v]) ret = max(ret, solve(v, G, V, bl));
	return ret;
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	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);
		cout << solve(0, G, V, bl) << "\n";
	}
	return 0;
}