#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;


struct Fenwick
{
	int n;
	vector<int> t;
	
	void init(int _n)
	{
		n = _n;
		t.clear();
		t.assign(n, 0);
	}
	void upd(int i, int x)
	{
		for(; i < n; i |= i + 1)
			t[i] += x;
	}
	int query(int i)
	{
		int ans = 0;
		for(; i >= 0; i = (i & (i + 1)) - 1)
			ans += t[i];
		return ans;
	}
}F;


const int N = 1 << 18;

VI g[N];
int w[N];

LL solve(vector<pair<int, LL>> vals, int cent)
{
	vector<LL> sums(SZ(vals));
	FOR(i, 0, SZ(vals))
		sums[i] = vals[i].S;
	
	sort(ALL(vals));
	sort(ALL(sums));
	
	F.init(SZ(sums));
	
	LL res = 0;
	for(auto [m, s] : vals)
	{
		//2 * max(m, w[cent]) + 1 <= s + s' + w[cent]
		//s' >= 2 * max + 1 - s - w[cent];
		LL low = 2 * max(m, w[cent]) + 1 - s - w[cent];
		int pos = lower_bound(ALL(sums), low) - sums.begin();
		
		res += F.query(SZ(sums) - 1) - F.query(pos - 1);
		
		pos = lower_bound(ALL(sums), s) - sums.begin();
		F.upd(pos, 1);
	}
	return res;
} 




int sz[N];
bool usedC[N];

int dfsSZ(int v, int par)
{
	sz[v] = 1;
	for(auto to : g[v])
	{
		if(to != par && !usedC[to])
			sz[v] += dfsSZ(to, v);
	}
	return sz[v];
}


vector<pair<int, LL>> verts;
void dfs(int v, int par, int d, LL sum)
{
	d += w[v];
	sum += w[v];
	verts.PB({d, sum});
	
	for(int to : g[v])
	{
		if(to == par || usedC[to])
			continue;
		dfs(to, v, d, sum);	
	}
}

LL ans = 0;

void build(int u)
{
	dfsSZ(u, -1);
	int szAll = sz[u];
	int pr = u;
	while(true)
	{
		int v = -1;
		for(auto to : g[u])
		{
			if(to == pr || usedC[to])
				continue;
			if(sz[to] * 2 > szAll)
			{
				v = to;
				break;
			}
		}
		if(v == -1)
			break;
		pr = u;
		u = v;
	}
	int cent = u;
	usedC[cent] = true;
	
	vector<pair<int, LL>> vertsAll;
	
	for(int to : g[cent])
	{
		if(usedC[to])
			continue;
		dfs(to, cent, 0, 0);
		ans -= solve(verts, cent);
		
		vertsAll.insert(vertsAll.end(), ALL(verts));
		verts.clear();
	}
	ans += solve(vertsAll, cent);
	
	for(auto to : g[cent])
	{
		if(!usedC[to])
		{
			build(to);
		}
	}
}


void solve()
{
	int n;
	cin >> n;
	FOR(i, 0, n)
		cin >> w[i];
	FOR(i, 0, n - 1)
	{
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].PB(b);
		g[b].PB(a);
	}
	ans = 0;
	build(0);
	cout << ans << "\n";
	
	FOR(i, 0, n)
	{
		g[i].clear();
		usedC[i] = 0;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while(t--)
		solve();
	
	
	return 0;
}
dead

answer.code:200:1: error: ‘dead’ does not name a type
  200 | dead
      | ^~~~