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
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using D = double;
#define f1 first
#define f2 second
#define randint(a, b) uniform_int_distribution<int>{a, b}(gen)
#ifdef LOC
void OUT() {cout << '\n';}
template<class H, class ... T> void OUT(H h, T ... t)
{
	cout << h << ' ';
	OUT(t...);
}
#define P(...) cout << "[" << #__VA_ARGS__ << "] ", OUT(__VA_ARGS__)
#else
#define P(...)
#define OUT(...)
#endif
vector<pair<int, int>> g[400];
int odw[400];
int odwVal = 1;
int t, n;
LL val[400];
int mask;

LL dfs(int p)
{
	LL sum = 0;
	sum += val[p];
	odw[p] = odwVal;
	for(auto pp : g[p])
	{
		if(odw[pp.f1] == odwVal) continue;
		if(pp.f2 & mask) continue;
		sum += dfs(pp.f1);
	}
	return sum;
}

LL ans[400];
void dp()
{
	LL toRet = 0;
	for(int i = 1; i <= n; ++i)
	{
		if(odw[i] != odwVal) 
		{
			LL sm = dfs(i);
			toRet += sm * sm;
		}
	}
	odwVal ^= 1;
	auto & o = ans[__builtin_popcount(mask)];
	o = min(o, toRet);
}
int main(int, char ** /*args*/)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while(t--)
	{
		cin >> n;
		for(int i = 1; i <= n; ++i)
		{
			cin >> val[i];
			g[i].clear();
		}
		for(int i = 0; i < n - 1; ++i)
		{
			int b, c;
			cin >> b >> c;
			g[b].push_back({c, 1<<i});
			g[c].push_back({b, 1<<i});
		}
		for(int i = 0; i < n; ++i)
		{
			ans[i] = 1e18;
		}
		for(int k = 0; k < 1<<(n - 1); ++k)
		{
			mask = k;
			dp();
		}
		for(int i = 0; i < n; ++i) cout << ans[i] << ' ';
		cout << '\n';
	}
	return 0;
}