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
#include<bits/stdc++.h>
#define lim 309
#define linf (1ll<<60)

typedef unsigned int uint;

using namespace std;

int n,T,k;
long long t[lim],tab[lim],w[lim];
vector<int> v[lim],ver,m;

void organize(int i,int p)
{
	for(uint j = 1;j<v[i].size();++j)
	{
		if(v[i][j]==p)
		{
			swap(v[i][j],v[i][0]);
		}
		organize(v[i][j],i);
	}
	ver.push_back(i);
}

void f(int i)
{
	if(i>=n)
	{
		for(int j = 0;j<=n;++j)
		{
			t[j] = tab[j];
		}
		long long wyn = 0;
		int pom = 0;
		for(int j = 0;j<n-1;++j)
		{
			if(m[j]==0)
			{
				t[v[ver[j]][0]] += t[ver[j]];
			}
			else
			{
				wyn += (long long)t[ver[j]]*t[ver[j]];
				++pom;
			}
		}
		wyn += (long long)t[ver.back()]*t[ver.back()];
		w[pom] = min(w[pom],wyn);
	}
	else
	{
		m.push_back(0);
		f(i+1);
		m.back() = 1;
		f(i+1);
		m.pop_back();
	}
}


int main()
{
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		for(int i = 1;i<=n;++i)
		{
			scanf("%lld", &tab[i]);
			w[i-1] = linf;
			if(v[i].size()) v[i].clear();
		}
		for(int i = 1;i<n;++i)
		{
			int a,b;
			scanf("%d%d", &a, &b);
			v[a].push_back(b);
			v[b].push_back(a);
		}
		k = 1;
		for(int i = 2;i<=n;++i)
		{
			if(v[i].size()>v[k].size())
			{
				k = i;
			}
		}
		if(ver.size()) ver.clear();
		v[k].push_back(0);
		organize(k,0);
		f(1);
		for(int i = 0;i<n;++i)
		{
			printf("%lld ", w[i]);
		}
		printf("\n");
	}
	
}