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
//brut
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

constexpr int M=303;
constexpr long double oo = 1000'000'000'000'000'000.00;

struct krv{
	int a, b, ind;
};

bool off[M];
int power[M];
int totalpower[M];
long long ans[M];
vector<pair<int,int> >g[M];
vector<krv>k;

long long res;

void compute(int v, int p, bool lastoff){
	totalpower[v] = power[v];
	
	for(auto w:g[v]){
		if(w.first==p) continue;
		
		if(off[w.second]) compute(w.first,v,1);
		else compute(w.first,v,0);
		
		if(!off[w.second]) totalpower[v] += totalpower[w.first];
	}
	
	if(lastoff || v==1) res += (long long)totalpower[v]*totalpower[v];
}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int t, n, a, b, chosen;

	cin >> t;

	while(t--){
		cin >> n;
		
		for(int i=0; i<=n; i++) ans[i]=oo;
		
		for(int i=1; i<=n; i++) cin >> power[i];
		
		for(int i=1; i<n; i++){
			cin >> a >> b;
			g[a].push_back({b,i-1});
			g[b].push_back({a,i-1});
			k.push_back({a,b,i-1});
		}
		
		for(int i=0; i<(1<<n); i++){
			res = chosen = 0;
			
			for(int j=0; j<k.size(); j++){
				if((1<<j)&i){
					off[j]=1;
					chosen++;
				}
				else off[j]=0;
			}
			
			compute(1,0,0);
			
			ans[chosen] = min(ans[chosen], res);
		}
		
		for(int i=0; i<n; i++) cout << ans[i] << ' ';
		cout << '\n';
		
		for(int i=1; i<=n; i++) g[i].clear();
		k.clear();		
	}
	
	return 0;
}
/*
2
7
9 1 4 2 6 4 7
1 7
6 4
2 3
5 7
3 4
5 3
5
4 8 2 3 1
4 3
3 1
4 2
5 1
*/