#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef double lf;
typedef long double llf;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
#define For(i,s,a) for(int i = (int)s; i < (int)a; ++i)
#define rpt(s, it) for(auto it = s.begin(); it != s.end(); ++it)
#define brpt(s, it) for(auto it = s.rend(); it != s.rbegin(); --it)
#define sz size()
#define pb push_back
#define eb emplace_back
#define ff first
#define dd second
#define mp make_pair
#define all(x) (x).begin (x).end()
#define ZAPS {int t; scanf("%i", &t); while(t--) solve();}


template<typename Ta, typename Tb>
ostream & operator <<(ostream & os, pair<Ta, Tb> x){
	return os << x.ff << " " << x.dd;
}



const int N = 3e2 + 1;
const int inf = 0x3f3f3f3f;

lld w[N];
vector<int>c[N];
pll dp[N][N];
pll solution[N];
pll basic[N][N];
pll old[N];
pll minx[N];
lld sum[N];
int cnt[N];

bitset<1048576>con;
lld ppp[1048576][20];

void zer0(int a){
	con = 0;
	memset(ppp, 0, sizeof(ppp));
	For(i, 0, a + 1)
		c[i].clear(),
		memset(dp[i], inf, sizeof(dp[i][0]) * (a + 1));
	memset(sum, 0, sizeof(sum[0]) * (a + 1));
	memset(cnt, 0, sizeof(cnt[0]) * (a + 1));
	memset(solution, inf, sizeof(solution[0]) * (a + 1));
}

void read(int &a){
	//scanf("%d", &a);
	//a = 300;
	zer0(a);
	For(i, 1, a + 1)
		scanf("%lld", &w[i]);
	//	w[i] = 3;
	For(i, 0, a - 1){
		int g, h;
		scanf("%d%d", &g, &h);
		//g = i + 1, h = i + 2;
		c[g].pb(h);
		c[h].pb(g);
	}
}

inline lld sq(lld x){
	return x * x;
}

void calc(int x, int a, int p = -1){
	memset(dp[x], inf, sizeof(dp[x][0]) * (a + 1));
	sum[x] = w[x];
	cnt[x] = 1;
	for(auto s : c[x])
		if(s != p)
			/*w[s] += w[x],
			calc(s, a, x),
			memcpy(basic[s], dp[s], sizeof(dp[s][0]) * (a + 1)),
			w[s] -= w[x],*/
			calc(s, a, x),
			memcpy(basic[s], dp[s], sizeof(dp[s][0]) * (a + 1)),
			sum[x] += sum[s];
			
			
			
	dp[x][1] = mp(sum[x] * sum[x], sum[x] * sum[x]);;
	For(i, 0, c[x].sz)
		if(c[x][i] == p){
			swap(c[x][i], c[x][c[x].sz - 1]);
			break;
		}
	lld maxmask = 1 << (c[x].sz - 1 + (p == -1));
	memset(minx, 0x3f3f3f3f, sizeof(minx[0]) * 302);
	
	For(mask, 0, maxmask){
		cnt[x] = 1;
		memset(dp[x], 0x3f3f3f3f, sizeof(dp[x][0]) * (302));
		dp[x][1] = mp(sum[x] * sum[x], sum[x] * sum[x]);
		For(i, 0, c[x].sz - 1 + (p == -1)){
			int s = c[x][i];
			memcpy(old, dp[x], sizeof(dp[x][0]) * (302));
			
			For(k, 1, cnt[s] + 1)
			For(dop, 1, cnt[x] + 1){
				lld rest = (1 << i) & mask ? basic[s][k].ff - basic[s][k].dd : dp[s][k].ff - dp[s][k].dd;
				lld main_ = (1 << i) & mask ? basic[s][k].dd : dp[s][k].dd;
				lld rest_top = old[dop].ff - old[dop].dd;
				lld main_top = old[dop].dd;
				
		//		cout<<mask<<"   "<<x<<" "<<s<<" "<<k<<" "<<dop<<"   "<<rest_top<<" "<<main_top<<"   "<<rest<<" "<<main_<<endl;
				
				if((1 << i) & mask){
					lld base = sq(sqrtl(main_top) - sum[s] + sqrtl(main_));
					lld cand = base + rest + rest_top;
		//			cout<<cand<<" A "<<endl;
					if(cand < dp[x][dop + k - 1].ff)
						dp[x][dop + k - 1] = mp(cand, base);
				}
				else{
					lld base = sq(sqrtl(main_top) - sum[s]);
		///			cout<<main_top<<" TFQ "<<sum[s]<<endl;
					lld cand = base + rest_top + rest + main_;
		///			cout<<cand<<" W "<<endl;
					if(cand < dp[x][dop + k].ff)
						dp[x][dop + k] = mp(cand, base);
				}
			}	
			cnt[x] += cnt[s];
		}
		//cout<<mask<<" JAJCO ";
		int nic = 1;
		For(st, 1, cnt[x] + 1)
			minx[st] = min(minx[st], dp[x][st]),
		//	cout<<dp[x][st].ff<<" ",
			nic = nic;
		//puts("\n");
	}
	For(st, 1, cnt[x] + 1)
		dp[x][st] = minx[st];
/*	cout<<x<<" i po "<<sum[x]<<" indiansku "<<cnt[x]<<endl;
	For(i, 1, cnt[x] + 1)
		cout<<dp[x][i].ff<<" ";
	puts("\n");
*/}

pii dft(int x, int a, bool half = 0, int p = -1, int dst = 0){
	pii mywyn = mp(dst, x);
	if(half && dst * 2 >= a)
		return mp(x, x);
	for(auto s : c[x])
		if(s != p)
			mywyn = max(mywyn, dft(s, a, half, x, dst + 1));
	return mywyn;
}

void solve(int a, int start){
	calc(start, a);
	For(i, 1, a + 1)
		solution[i] = min(solution[i], dp[start][i]);
}

bool check(int x){
	int par[20];
	For(i, 0, 20)
		par[i] = i;
	For(i, 0, 20)
		if((1 << i) & x)
			for(auto s : c[i]){
				if((1 << s) & x){
				int si = par[i];
				while(si != par[si])
					si = par[si];
				int ss = par[s];
				while(ss != par[ss])
					ss = par[ss];
				int minxx = min(ss, si);
				par[si] = par[ss] = minxx;}
			}
	int cnd = par[(int)log2(x & (-x))];
	while(cnd != par[cnd])
		cnd = par[cnd];
	For(i, 0, 20)
		if(((1 << i) & x)){
			int ptx = par[i];
			while(ptx != par[ptx])
				ptx = par[ptx];
			if(ptx != cnd)
				return 0;
		}
	return 1;		
}

void slowread(int &a){
	zer0(a);
	//a = 300;
	For(i, 0, a)
		scanf("%lld", &w[i]);
	//	w[i] = 3;
	For(i, 0, a - 1){
		int g, h;
		scanf("%d%d", &g, &h);
		--g;--h;
		//g = i + 1, h = i + 2;
		c[g].pb(h);
		c[h].pb(g);
	}
}

void slowsolve(int a){
	slowread(a);
	con[0] = 1;
	int maxmask = 1 << a;
	lld maxcnt = 1e18;
	For(i, 1, maxmask){
		For(len, 1, a + 1)
		ppp[i][len] = maxcnt;
		con[i] = check(i);
	}
	For(mask, 1, maxmask){
		if(!con[mask])
			continue;
		ppp[mask][1] = 0;
		For(j, 0, a)
			if((1 << j) & mask)
				ppp[mask][1] += w[j];
		ppp[mask][1] *= ppp[mask][1];
		for(int xd = mask; xd; xd = (mask & (xd - 1))){
			if(con[xd] && con[mask ^ xd])
			For(l, 1, a + 1)
			For(k, 1, a + 1 - l)
				ppp[mask][l + k] = min(ppp[mask][l + k], ppp[xd][l] + ppp[mask ^ xd][k]);
		}
	}
	For(l, 1, a + 1)
		printf("%lld ", ppp[maxmask - 1][l]);
	puts("");
}

void solve(void){
	int a;
	scanf("%d", &a);
	if(a < 17){
		slowsolve(a);
		return;
	}
	read(a);
	int rands[a];
	For(i, 0, a)
		rands[i] = i + 1;
	random_shuffle(rands, rands + a);
	For(i, 1, min(160, a + 1)){
		//printf("%d\n", rands[i - 1]);
		solve(a, rands[i - 1]);
	}
	For(i, 1, a + 1)
		printf("%lld ", solution[i].ff);
	puts("");
}

int main(){
	ZAPS
}

/*
2
4
4 3 2 7
1 2
2 3
2 4

7
4 3 2 5 9 2 7
1 2
1 3
1 4
1 5
2 6
2 7
*/

/*
2
7
9 1 4 2 6 4 7
1 7
6 4
2 3
5 7
3 4
5 3
5
4 8 2 3 1
4 3
3 1
4 2
5 1
*/