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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <bits/stdc++.h>

using namespace std;

const long long M = 100000000000000000;

int n;
int a[305];
vector < int > E[305];
vector < int > children[305];
int parent[1000];

struct option
{
	long long up_sum;
	int k;
	long long S2;
};

bool comp(option a, option b){
	return a.up_sum > b.up_sum;
}

vector < int > out;
vector < option > options[400];

bool used[305];
void dfs(int vertex){
	used[vertex] = true;

	for(int v : E[vertex]){
		if(!used[v]){
			dfs(v);
			children[vertex].push_back(v);
			parent[v] = vertex;
		}
	}
	// Uwaga na n = 2 !!!!
	if(E[vertex].size() == 1 and vertex != 1){
		option o;
		o.up_sum = a[vertex];
		o.k = 0;
		o.S2 = 0;
		options[vertex].push_back(o);
	}
	out.push_back(vertex);
}


int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);

	int t;
	cin >> t;
	while(t--){
		cin >> n;
		for (int i = 1; i <= n; ++i)
		{
			cin >> a[i];
		}
		for (int i = 0; i < 304; ++i)
		{
			E[i].clear();
			used[i] = false; 
			//active[i] = true;
			options[i].clear();
			out.clear();
			children[i].clear();
		}
		for (int i = 0; i < n - 1; ++i)
		{
			int x, y;
			cin >> x >> y;
			E[x].push_back(y);
			E[y].push_back(x);
		}		dfs(1);

		for(int vertex : out){
			if(children[vertex].size() == 0)	continue;
			//cout << endl << endl << "vertex = " << vertex << endl;
			// usuwam wierzchołek vertex
			long long max_mask = 1;
			for(int v : children[vertex]){
				max_mask *= options[v].size();
			}
			//cout << "max_mask = " << max_mask << endl;
			for (long long mask = 0; mask < max_mask; ++mask)
			{
				
				long long cur_mask = mask;
				vector < option > cur_options;
				int k_total = 0;
				long long S2_total = 0;
				long long up_total = 0;
				for(int v : children[vertex]){
					int cur_opt = cur_mask % options[v].size();
					//cout << cur_opt << endl;
					cur_mask /= options[v].size();
					cur_options.push_back(options[v][cur_opt]);
					k_total += options[v][cur_opt].k;
					S2_total += options[v][cur_opt].S2;
					up_total += options[v][cur_opt].up_sum;
				}

				sort(cur_options.begin(), cur_options.end(), comp);

				long long up_pref = 0;
				long long S2_pref = 0;
				//cout << "up_total = " << up_total << endl;
				for (int i = 0; i <= cur_options.size(); ++i)
				{
					// i pierwszych uwalamy
					option o;
					o.up_sum = up_total - up_pref + a[vertex];
					o.S2 = S2_total + S2_pref;
					o.k = i + k_total;

					options[vertex].push_back(o);

					if(i == cur_options.size())	break;

					// biorę tylko i kolejnych
					up_pref += cur_options[i].up_sum;
					S2_pref += cur_options[i].up_sum * cur_options[i].up_sum;
				}
			}
		}

		long long minima[400];
		for (int i = 0; i < 400; ++i)
		{
			minima[i] = M;
		}

		for(option o : options[1]){
			long long s = o.S2 + o.up_sum * o.up_sum;
			minima[o.k] = min(minima[o.k], s);
		}


		for (int i = 0; i < n; ++i)
		{
			cout << minima[i] << " ";
		}
		cout << endl;
	}
}