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
#include <cstdio>
#include <vector>
using namespace std;

int n;
bool vis[305];
long long a[305], r[305];

vector<pair<int,int>> edges;
vector<int> e[305];

long long dfs(int start){
	vis[start] = true;
	long long r = a[start];
	for (int v : e[start]){
		if (!vis[v]){
			r += dfs(v);
		}
	}
	return r;
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--){
		scanf("%d", &n);
		int m = 0, mx = 1;
		for (int i = 1; i <= n; i++){
			scanf("%lld", &a[i]);
			mx *= 2;
		}
		mx /= 2;
		for (int i = 0; i < n - 1; i++){
			int b, c;
			scanf("%d%d", &b, &c);
			edges.push_back(make_pair(b, c));
		}
		for (int i = 1; i <= n; i++){
			r[i] = 1000000000000000LL;
		}
		while (m < mx){
			for (int i = 0; i < n - 1; i++){
				if (!(m & (1 << i))){
					int b, c;
					b = edges[i].first;
					c = edges[i].second;
					e[b].push_back(c);
					e[c].push_back(b);
				}
			}
			int s = 0;
			long long tr = 0;
			for (int i = 1; i <= n; i++){
				if (!vis[i]){
					s++;
					long long v = dfs(i);
					//printf("aa %lld %d\n", v, i);
					tr += v * v;
				}
			}
			r[s] = min(r[s], tr);
			for (int i = 1; i <= n; i++){
				e[i].clear();
				vis[i] = false;
			}
			m++;
		}
		for (int i = 1; i <= n; i++){
			printf("%lld ", r[i]);
		}
		printf("\n");
		edges.clear();
	}
}