#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,root=0;
const ll inf=1e18;
vector<int> g[310];
int father[310];
int block[310];
ll weight[310];
int cnt=0;
vector<int> where;
int cand_where[12345670];
int col[12345670];
ll ans;
ll prop_change[12345670];
queue<int> q;
set<pair<ll,int> > sett;
void dfs1(int v,int p){
	father[v]=p;
	for(int u : g[v]){
		if(u==p)continue;
		dfs1(u,v);
	}
}
void process(vector<pair<int,int> > graph){
	for(auto pr : graph){
		g[pr.first].push_back(pr.second);
		g[pr.second].push_back(pr.first);
	}
	dfs1(root,-1);
}
vector<pair<int,int> > read_graph(){
	vector<pair<int,int> > ans(n-1);
	for(int i=0;i<n-1;i++){
		int a,b;
		cin >>a >>b;
		ans[i]={a-1,b-1};
	}
	return ans;
}
int random_int(int a, int b) { return a + rand() % (b - a + 1); }
vector<pair<int,int> > random_tree(int n) {
  vector<int> l1, l2;
  vector<pair<int, int>> edges;

  for (int i = 0; i < n - 2; i++)
    l1.push_back(random_int(1, n));
  for (int i = 0; i < n; i++)
    l2.push_back(i + 1);

  while ((int)l2.size() > 2) {
    for (int i : l2) {
      if (find(l1.begin(), l1.end(), i) != l1.end()) {
        continue;
      }

      edges.push_back({i, l1[0]});
      l1.erase(l1.begin());
      l2.erase(find(l2.begin(), l2.end(), i));
      break;
    }
  }
  edges.push_back({l2[0], l2[1]});
  for (int i = 0; i < (int)edges.size(); ++i) {
    swap(edges[i], edges[random_int(0, i)]);
  }
  for(auto &pr : edges){
  	pr.first--;pr.second--;
  }
  return edges;
}
int dfs2(vector<int> &vis,int v){
	if(vis[v])return 0;
	vis[v]=1;
	int ans=weight[v];
	for(int u : g[v]){
		if(u==father[v]){
			if(block[v])continue;
			ans+=dfs2(vis,u);
		}
		else{
			if(block[u])continue;
			ans+=dfs2(vis,u);
		}
	}
	return ans;
}
int get_son(int v,int u){
	if(u<0)return v;
	if(father[u]==v){
		return u;
	}
	return v;
}
ll get_ans(){
	ll ans=0;
	vector<int> vis(n);
	for(int i=0;i<n;i++){
		if(!vis[i]){
			ll temp=dfs2(vis,i);
			ans+=temp*temp;
		}
	}
	return ans;
}
void init(){
	cnt=0;
	for(int i=0;i<310;i++){
		g[i].clear();
		father[i]=block[i]=weight[i]=0;
	}
	cin >>n;
	for(int i=0;i<n;i++){
		cin >>weight[i];
	}
	process(read_graph());
	
	/*
	for(int i=0;i<n;i++){
		weight[i]=random_int(1,10);
	}
	process(random_tree(n));*/
}
ll dfs3(vector<pair<ll,pair<int,int> > > &poss, int v, int p){
	col[v]=cnt;
	int ans=weight[v];
	for(int u : g[v]){
		if(u==p)continue;
		if(u==father[v]){
			if(block[v])continue;
			ans+=dfs3(poss,u,v);
		}
		else{
			if(block[u])continue;
			ans+=dfs3(poss,u,v);
		}
	}
	poss.push_back({ans,{v,p}});
	return ans;
}
void add_area(int x){
	cnt++;
	vector<pair<ll,pair<int,int> > > poss;
	random_shuffle(poss.begin(),poss.end());
	ll sum = dfs3(poss,x,-1);
	ll best = inf;
	int which = -1;
	for(int i=0;i<poss.size();i++){
		ll here = (sum-poss[i].first)*(sum-poss[i].first)+(poss[i].first)*(poss[i].first);
		if(here < best){
			best = here;
			which = i;
		}
	}
	prop_change[cnt]=best-sum*sum;
	sett.insert({best-sum*sum,cnt});
	if(which!=-1){
		if(father[poss[which].second.first] == poss[which].second.second){
			cand_where[cnt]=poss[which].second.first;
		}
		else{
			cand_where[cnt]=poss[which].second.second;
		}
	} 
}
void del_block(int v){
	block[v]=0;
	sett.erase({prop_change[col[v]],col[v]});
	sett.erase({prop_change[col[father[v]]],col[father[v]]});
	add_area(v);
}
int best_place2(){
	int place = (*sett.begin()).second;
	sett.erase(sett.begin());
	block[cand_where[place]]=1;
	where.push_back(cand_where[place]);
	add_area(cand_where[place]);
	add_area(father[cand_where[place]]);
	return cand_where[place];
}
void change(){
	if(where.size()==0)return;
	int loop=0;
	while(true){
		loop++;
		int act=0;
		vector<int> vec;
		for(int i=1;i<n;i++){
			vec.push_back(i);
		}
		random_shuffle(vec.begin(),vec.end());
		for(int v : vec){
			if(!block[v])continue;
			del_block(v);
			int u = best_place2();
			if(v==u)continue;
			act=1;	
		}
		if(act==0 || loop>20)break;
		//cout <<"spin ";
	}
}

void sol(){
	add_area(0);
	for(int i=0;i<n;i++){
		cout <<get_ans() <<" ";
		best_place2();
		change();
	}
	cout <<"\n";
}
void test(){
	init();
	sol();
}
int main(){
	srand(2137);
	int t;
	cin >>t;
	while(t--){
		test();
	}
}