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
#include <bits/stdc++.h>
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define TRAV(i, a) for(auto & i : (a))
#define SZ(x) ((int)(x).size())
#define PR std::pair
#define MP std::make_pair
#define X first
#define Y second
typedef long long ll;
typedef std::pair<int, int> PII;
typedef std::pair<ll, ll> PLL;
typedef std::vector<int> VI;

struct S{
	std::vector<PLL> vec;

	void fix(){
		std::vector<PLL> nw;
		std::sort(vec.begin(), vec.end());
		TRAV(i, vec){
			if(nw.empty() || nw.back().Y > i.Y)
				nw.push_back(i);
		}
		vec = nw;
	}

	void add(PLL p){
		vec.push_back(p);
	}

	void add(const S& ot){
		TRAV(i, ot.vec) add(i);
	}

	friend S operator *(const S& A, const S& B){
		S ret;
		TRAV(i, A.vec) TRAV(j, B.vec) ret.add(MP(i.X+j.X+i.Y*j.Y, i.Y+j.Y));
		ret.fix();
		return ret;
	}

	ll ans(){
		assert(SZ(vec));
		return vec[0].X;
	}
};

void cut(std::vector<S>& vec){
	vec.emplace_back();
	for(int i = SZ(vec)-2; i >= 0; --i){
		vec[i+1].add(MP(vec[i].ans(), 0));
		vec[i+1].fix();
	}
}

std::vector<S> conv(const std::vector<S>& a, const std::vector<S>& b){
	std::vector<S> ret(SZ(a)+SZ(b)-1);
	FOR(i, SZ(a)){
		FOR(j, SZ(b)){
			ret[i+j].add(a[i]*b[j]);
		}
	}
	FOR(i, SZ(ret)) ret[i].fix();
	return ret;
}

VI A;
std::vector<VI> g;
std::vector<S> dfs(int v, int par=-1){
	std::vector<S> ret;
	ret.push_back(S());
	ret.back().add(MP(0, A[v]));
	TRAV(ch, g[v]) if(ch != par){
		auto xd = dfs(ch, v);
		cut(xd);
		ret = conv(ret, xd);
	}
	return ret;
}

void solve(){
	int n;
	std::cin >> n;
	A.resize(n);
	ll sum = 0;
	FOR(i, n) std::cin >> A[i], sum += 1ll*A[i]*A[i];
	g = std::vector<VI>(n);
	FOR(i, n-1){
		int a, b;
		std::cin >> a >> b;
		a--;b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	auto ret = dfs(0);
	FOR(i, n){
		if(i != 0) std::cout << " ";
		std::cout << 2ll*ret[i].ans() + sum;
	}
	std::cout << "\n";
}

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

	int t;
	std::cin >> t;
	while(t--) solve();

	return 0;
}