1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

#define st first
#define nd second
#define PLL pair <LL, LL>

const int N = 307;

int n;
int sz[N];
int vals[N];
vector <int> G[N];

vector <PLL> tmp[N];
vector <PLL> dp[N][N];

void read() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &vals[i]);
	
	for(int i = 1; i < n; ++i) {
		int u, v;
		scanf("%d %d", &u, &v);
		
		G[u].push_back(v);
		G[v].push_back(u);
	}
}

vector <PLL> parse(vector <PLL> &in) {
	sort(in.begin(), in.end());
	vector <PLL> result;
	
	for(auto [s, v]: in) {
		if(result.size() == 0)
			result.push_back({s, v});
		else {
			auto [s2, v2] = result.back();
			if(s2 * s2 + v2 > s * s + v)
				result.push_back({s, v});
		}
	}
	
	return result;
}

void push(vector <PLL> &to_push, const vector <PLL> &Left, const vector <PLL> &Right) {
	for(const auto &[ls, lv] : Left)
		for(const auto &[rs, rv]: Right)
			to_push.push_back({ls + rs, lv + rv});
}

void merge(int &fa, int &fb) {
	for(int i = 0; i < sz[fa] + sz[fb]; ++i)
		tmp[i].clear();
	
	for(int ca = 0; ca < sz[fa]; ++ca) {
		for(int cb = 0; cb < sz[fb]; ++cb) {
			push(tmp[ca + cb], dp[fa][ca], dp[fb][cb]);
			
			auto [ts, tv] = dp[fb][cb].back();
			for(auto [s, v]: dp[fa][ca])
				tmp[ca + cb + 1].push_back({s, v + tv + ts * ts});
		}
	}
	
	sz[fa] += sz[fb];
	for(int i = 0; i < sz[fa]; ++i) {
		dp[fa][i] = parse(tmp[i]);
	}
}

void go(int u, int p) {
	sz[u] = 1;
	dp[u][0] = {{vals[u], 0}};
	for(auto v: G[u])
		if(v != p) {
			go(v, u);
			merge(u, v);
		}
}

void solve() {
	/* TODO?: Pick centroid as root */
	go(1, 0);
}

void write() {
	for(int i = 0; i < n; ++i) {
		auto [s, v] = dp[1][i].back();
		printf("%lld%c", s * s + v, " \n"[i + 1 == n]);
	}
}

void clear() {
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j < sz[i]; ++j)
			dp[i][j].clear();
		
		sz[i] = 0;
		G[i].clear();
	}
}

int main() {
	int tests;
	scanf("%d", &tests);
	
	while(tests--) {
		read();
		solve();
		write();
		clear();
	}

	return 0;
}