#include <ctime>
#include <cmath>
#include <cassert>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#include <unordered_map>

using i64 = long long;
using u64 = long long;

const int N = 300 + 10;

u64 hs[N];
std::vector<int> edges[N];
int dis[N], parent[N], size[N];
int st[N], ed[N], pos[N], sz;
int a[N], sum[N];
int n;

void dfs(int u, int p = -1) {
  if (p == -1) dis[u] = 1;
  else dis[u] = dis[p] + 1;
  size[u] = 1;
  parent[u] = p;
  pos[sz] = u;
  st[u] = sz++;
  sum[u] = a[u];
  for (auto &v: edges[u]) if (v != p) {
    dfs(v, u);
    size[u] += size[v];
    sum[u] += sum[v];
  }
  ed[u] = sz;
}

int get_center() {
  sz = 0; dfs(0);
  int r = std::max_element(dis, dis + n) - dis;
  sz = 0; dfs(r);
  r = std::max_element(dis, dis + n) - dis;
  int diameter = dis[r];
  for (int i = 0; i < diameter / 2; ++i) {
    r = parent[r];
  }
  sz = 0; dfs(r);
  return r;
}

std::unordered_map<u64, std::vector<i64>> cache;
std::vector<int> subtree[N];
std::vector<std::pair<int, i64>> dp[N][N];
i64 ret[N][N];

void add(std::vector<std::pair<int, i64>> &u, int x, i64 y) {
  if (u.empty()) {
    u.emplace_back(x, y);
    return;
  }
  auto v = std::make_pair(x, y);
  int r = std::lower_bound(u.begin(), u.end(), std::make_pair(x + 1, i64(1))) - u.begin();
  if (r && u[r - 1].second <= y) return;
  int l = r - 1;
  if (l >= 0 && u[l].first == x) --l;
  while (r < u.size() && u[r].second >= y) ++r;
  if (l + 1 == r) {
    u.insert(u.begin() + l + 1, v);
    if (l >= 0) assert(u[l].first < v.first);
  } else {
    u[l + 1] = v;
    for (size_t i = r; i < u.size(); ++i) {
      u[l + 2 + i - r] = u[i];
    }
    u.resize(l + 2 + u.size() - r);
  }
}

void solve_small_subtree(int u, int p = -1) {
  subtree[u] = {u};
  for (auto &v: edges[u]) if (v != p) {
    solve_small_subtree(v, u);
    for (auto &x: subtree[v]) subtree[u].push_back(x);
  }
  if (size[u] > 50) return;
  // [st[u], ed[u])
  for (int i = st[u]; i <= ed[u]; ++i) {
    for (int j = 0; j < size[u]; ++j) {
      dp[i][j].clear();
    }
  }
  dp[st[u]][0].emplace_back(a[u], 0);
  for (int i = st[u] + 1; i < ed[u]; ++i) {
    int v = pos[i], w = a[v];
    for (int j = 0; j < size[u]; ++j) {
      if (dp[i - 1][j].empty()) continue;
      // choose
      for (auto &e: dp[i - 1][j]) {
        add(dp[i][j], e.first + w, e.second);
      }
      // not choose
      for (auto &e: dp[i - 1][j]) {
        for (int k = 0; k < size[v]; ++k) {
          add(dp[ed[v] - 1][j + 1 + k], e.first, e.second + ret[v][k]);
        }
      }
    }
  }
  u64 hash = 0;
  for (auto &x: subtree[u]) hash += a[x] * hs[x];
  for (int i = 0; i < size[u]; ++i) {
    ret[u][i] = -1;
    for (auto &e: dp[ed[u] - 1][i]) {
      i64 w = e.second + (i64)e.first * e.first;
      if (ret[u][i] == -1 || ret[u][i] > w) ret[u][i] = w;
    }
  }
  cache[hash] = std::vector<i64>(ret[u], ret[u] + size[u]);
}

namespace run {
int size[N], deg[N];
int ret_u, ret_v, mins, total;
int vs[N], nv;
u64 cur_hash;

void get_split(int u, int p = -1) {
  vs[nv++] = u;
  cur_hash += a[u] * hs[u];
  size[u] = 1;
  deg[u] = (p != -1);
  for (auto &v: edges[u]) if (v != p) {
    ++deg[u];
    get_split(v, u);
    if (std::abs(total - size[v] - size[v]) < mins) {
      mins = std::abs(total - size[v] - size[v]);
      ret_u = u, ret_v = v;
    }
    size[u] += size[v];
  }
}

std::vector<i64> solve_star(int u) {
  std::vector<i64> w;
  i64 sum = a[u];
  for (auto &v: edges[u]) w.push_back(a[v]);
  for (auto &x: w) sum += x;
  std::sort(w.begin(), w.end());
  std::vector<i64> ret(w.size() + 1);
  ret[0] = sum * sum;
  i64 now = 0;
  for (size_t i = 1; i < ret.size(); ++i) {
    sum -= w.back();
    now += w.back() * w.back();
    ret[i] = now + sum * sum;
    w.pop_back();
  }
  return ret;
}

std::vector<i64> rec(int r, int _tot) {
  total = mins = _tot;
  cur_hash = 0;
  nv = 0;
  get_split(r);
  int eu = ret_u, ev = ret_v;
  int sv = size[ev];
  int su = total - sv;
  if (cache.count(cur_hash)) return cache[cur_hash];
  // check star
  for (int i = 0; i < nv; ++i) {
    if (deg[vs[i]] + 1 == nv) return solve_star(vs[i]);
  }
  int pu = std::find(edges[ev].begin(), edges[ev].end(), eu) - edges[ev].begin();
  int pv = std::find(edges[eu].begin(), edges[eu].end(), ev) - edges[eu].begin();
  // merge eu and ev
  a[eu] += a[ev];
  edges[eu].erase(edges[eu].begin() + pv);
  for (auto &x: edges[ev]) if (x != eu) {
    edges[eu].push_back(x);
    for (auto &y: edges[x]) if (y == ev) {
      y = eu; break;
    }
  }
  auto ret = rec(eu, _tot - 1);
  ret.push_back(-1);
  a[eu] -= a[ev];
  for (auto &x: edges[ev]) if (x != eu) {
    edges[eu].pop_back();
    for (auto &y: edges[x]) if (y == eu) {
      y = ev; break;
    }
  }
  edges[eu].insert(edges[eu].begin() + pv, ev);
  // split eu and ev
  edges[ev].erase(edges[ev].begin() + pu);
  edges[eu].erase(edges[eu].begin() + pv);
  auto ru = rec(eu, su);
  auto rv = rec(ev, sv);
  edges[ev].insert(edges[ev].begin() + pu, eu);
  edges[eu].insert(edges[eu].begin() + pv, ev);
  for (int i = 0; i < su; ++i) {
    for (int j = 0; j < sv; ++j) {
      if (ret[i + j + 1] == -1 || ret[i + j + 1] > ru[i] + rv[j]) {
        ret[i + j + 1] = ru[i] + rv[j];
      }
    }
  }
  return ret;
}
}

int main(int argc, char **argv) {
  srand(time(NULL));
  int T;
  scanf("%d", &T);
  for (int cas = 1; cas <= T; ++cas) {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) hs[i] = (u64)rand() * rand();
    for (int i = 0; i < n; ++i) edges[i].clear();
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i < n; ++i) {
      int u, v;
      scanf("%d%d", &u, &v);
      --u, --v;
      edges[u].push_back(v);
      edges[v].push_back(u);
    }
    int r = get_center();
    cache.clear();
    solve_small_subtree(r);
    auto ret = run::rec(r, n);
    for (int i = 0; i < n; ++i) {
      if (i) putchar(' ');
      printf("%lld", ret[i]);
    }
    puts("");
  }
  return 0;
}