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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <cstring>

#define REP(a,n) for (int a = 0; a<(n); ++a)
#define FOR(a,b,c) for (int a = (b); a<=(c); ++a)
#define FORD(a,b,c) for (int a = (b); a>=(c); --a)
#define FOREACH(a,v) for (auto a : v)

#define MP make_pair
#define PB push_back

template<class T> inline int size2(const T&t) { return t.size(); }

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long LL;

///////////////////////////////

int N;
int val[300];
vector<int> sas[300];

void wstaw(map<int,LL> &res, int gora, LL cale) {
  {
    auto it = res.upper_bound(gora);
    if (it != res.begin()) {
      --it;
      if (it->second <= cale)
        return;
    }
  }
  for (;;) {
    auto it = res.lower_bound(gora);
    if (it != res.end() && cale <= it->second)
      res.erase(it);
    else
      break;
  }
  res[gora] = cale;
}

void merge(vector<map<int,LL>> &res, const vector<map<int,LL>> &gora, const vector<map<int,LL>> &dol) {
  res.resize(size2(gora) + size2(dol));
  for (int i = 0; i < size2(gora); ++i)
    for (int j = 0; j < size2(dol); ++j)
      for (auto ppG : gora[i]) {
        wstaw(res[i + j + 1], ppG.first, ppG.second + dol[j].rbegin()->second);
        for (auto ppD : dol[j])
          wstaw(res[i + j], ppG.first + ppD.first, ppG.second + ppD.second + 2 * ppG.first * (LL) ppD.first);
      }
}

void solve(int cur, vector<map<int,LL>> &res) {
  res.resize(1);
  res[0][val[cur]] = val[cur] * (LL)val[cur];
  vector<map<int,LL>> gora;
  for (int ch : sas[cur]) {
    vector<map<int,LL>> dol;
    swap(gora, res);
    solve(ch, dol);
    res.clear();
    merge(res, gora, dol);
  }
}

int DFS(int cur, int par) {
  vector<pii> ll;
  int ile = 1;
  for (auto ch : sas[cur])
    if (ch != par)
      ll.emplace_back(DFS(ch, cur), ch); 
  sort(ll.begin(), ll.end());
  sas[cur].clear();
  FORD(a, size2(ll) - 1, 0) {
    sas[cur].PB(ll[a].second);
    ile += ll[a].first;
  }
  return ile;
}

void licz() {
  cin >> N;
  REP(a, N) {
    cin >> val[a];
    sas[a].clear();
  }
  REP(a, N - 1) {
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    sas[x].PB(y);
    sas[y].PB(x);
  }
  DFS(0, -1);
  vector<map<int,LL>> res;
  solve(0, res);
  bool fst = 1;
  for (auto &mm : res) {
    if (fst)
      fst = 0;
    else
      cout << " ";
    cout << mm.rbegin()->second;
  }
  cout << endl;
}

int main() {
  int TT;
  cin >> TT;
  REP(tt, TT)
    licz();
}