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
#include <bits/stdc++.h>
using namespace std;

const int N = 305;
const long long inf = 1e18;

int t;
int n;
vector<pair<int, int> > kraw[N];
long long tab[N];
bool blocked[N];
bool odw[N];
long long dp[N];

long long dfs(int x) {
	odw[x] = true;
	long long res = tab[x];
	for (auto v : kraw[x]) {
		if (!odw[v.first] && !blocked[v.second]) {
			res += dfs(v.first);
		}
	}
	return res;
}

int main()
{
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			kraw[i].clear();
			dp[i] = inf;
		}
		for (int i = 1; i <= n; i++) {
			scanf("%lld", &tab[i]);
		}
		for (int i = 0; i < n - 1; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			kraw[a].push_back(make_pair(b, i));
			kraw[b].push_back(make_pair(a, i));
		}
		int maska = 0;
		int ile = (1 << (n-1));
		for (int i = 0; i < ile; i++) {
			int tmp = i;
			int ile = 0;
			for (int j = 0; j < n - 1; j++) {
				odw[j + 1] = false;
				blocked[j] = tmp % 2;
				ile += tmp % 2;
				tmp /= 2;
			}
			odw[n] = false;
			long long res = 0;
			for (int i = 1; i <= n; i++) {
				if (!odw[i]) {
					long long new_res = dfs(i);
					res += new_res*new_res;
				}
			}
			dp[ile + 1] = min(dp[ile + 1], res);
		}
		for (int i = 1; i <= n; i++) {
			printf("%lld ", dp[i]);
		}
		printf("\n");
	}
}