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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int TESTS, KEK, n, weight[305], a[305], b[305], r[305];
int Find(int x) {
	if(r[x] == x) return x;
	return r[x] = Find(r[x]);
}
ll ans[305], sum[305];
int32_t main() {
	ios_base::sync_with_stdio(0);
	cin >> TESTS;
	for(KEK = 1; KEK <= TESTS; KEK++) {
		cin >> n;
		for(int i = 1; i <= n; i++) {
			cin >> weight[i];
			ans[i] = 1e18;
		}

		for(int i = 1; i < n; i++) {
			cin >> a[i] >> b[i];
		}

		int m = n - 1;
		for(int mask = 0; mask < (1 << m); mask++) {
			int sp = n;
			for(int i = 1; i <= n; i++)
				r[i] = i, sum[i] = weight[i];

			for(int i = 1; i < n; i++) {
				if(mask >> (i - 1) & 1) {
					int ra = Find(a[i]), rb = Find(b[i]);
					sp--;
					sum[ra] += sum[rb];
					r[rb] = ra;
				}
			}

			ll res = 0;
			for(int i = 1; i <= n; i++)
				if(Find(i) == i)
					res += sum[i] * sum[i];

			ans[sp] = min(res, ans[sp]);
		}

		for(int i = 1; i <= n; i++) cout << ans[i] << " ";
		cout << "\n";
	}
}