#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define endl "\n"
#define mp make_pair
#define st first
#define nd second
#define pii pair<long long, int>
#define vpii vector<pii>
#define mpii vector<vpii>
#define pb push_back
#define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0);
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FWD(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fwd(i, a, b) for (int i = (a); i < (b); ++i)
#define all(c) (c).begin(), (c).end()
#define sz(X) (int)((X).size())
#define what(x) cerr << #x << " is " << x << endl;

ostream &operator<<(ostream &out, string str) {
   for (char c : str)
      out << c;
   return out;
}
template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; }
template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
   out << '{';
   for (auto it = a.begin(); it != a.end(); it = next(it))
      out << (it != a.begin() ? ", " : "") << *it;
   return out << '}';
}
void dump() { cerr << "\n"; }
template <class T, class... Ts> void dump(T a, Ts... x) {
   cerr << a << ", ";
   dump(x...);
}
#define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)

//#define int long long
const int MAXN = 301;
const long long inf = 1e18;
int R = 6;
double MULT = 2.0;
vector<int> G[MAXN];
int val[MAXN];
int sum[MAXN];
int rozmiar_poddrzewa[MAXN];
int n;
int avg;
long long ile = 0;

void pre() {
   rep(i, MAXN) G[i].clear();
   cin >> n;

   rep(i, n) cin >> val[i];

   rep(i, n - 1) {
      int a, b;
      cin >> a >> b;
      G[--a].emplace_back(--b);
      G[b].emplace_back(a);
   }
}

long double get_mult_help(long double x) {
   if (x <= 1.5)
      return 4.25;
   if (x <= 2)
      return 4.00;
   if (x <= 3)
      return 3.25;
   if (x <= 4)
      return 3.00;
   if (x <= 6)
      return 2.75;
   if (x <= 8)
      return 2.5;
   if (x <= 12)
      return 2.25;
   if (x <= 16)
      return 2;
   if (x <= 32)
      return 1.5;
   return 1.4;

   // if (x <= 2)
   //    return 4;
   // if (x <= 3)
   //    return 3.75;
   // if (x <= 4)
   //    return 3.25;
   // if (x <= 6)
   //    return 2.75;
   // if (x <= 8)
   //    return 2.5;
   // if (x <= 12)
   //    return 2.25;
   // if (x <= 16)
   //    return 1.8;
   // if (x <= 32)
   //    return 1.5;
   // if (x <= 64)
   //    return 1.4;
   // return 1.25;
}
double get_mult(long double x) { return get_mult_help(x) * 1.00; }

void combine(vpii &A, vpii &B, vpii &res, int val, int i, mpii &M) {
   int ogranicznie = i == 0 ? inf : get_mult((long double)sz(M) / i) * val / i;

   for (int i = sz(A) - 1; i >= 0; i--) {
      const int ogr = ogranicznie - A[i].nd;
      for (int j = sz(B) - 1; j >= 0 && B[j].nd <= ogr; j--)
         //  if (A[i].nd + B[j].nd <= ogranicznie)
         res.emplace_back(A[i].st + B[j].st, A[i].nd + B[j].nd);
   }
   // else
   //    break;
   // for (auto a : A)
   //    for (auto b : B) {
   //       if (a.nd + b.nd <= ogranicznie)
   //          res.emplace_back(a.st + b.st, a.nd + b.nd);
   //    }
}

vpii normalize(vpii &A) {
   if (sz(A) == 0)
      return A;

   //  std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();

   sort(all(A));
   // std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();

   // ile += std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count();

   vpii B = {A[0]};
   B.reserve(sz(A));
   for (int i = 1; i < sz(A); i++)
      if (B.back().nd > A[i].nd)
         B.push_back(A[i]);
   return B;
}

// void remove_big(mpii &M, long long val) {
//    //  return;
//    for (int i = 0; i < sz(M); i++) {
//       int ogranicznie = i == 0 ? inf : get_mult((long double)sz(M) / i) * val / i;
//       while (!M[i].empty() && M[i].front().nd > ogranicznie) {
//          debug("AAAA");
//          M[i].pop_front();
//       }
//    }
// }

void remove_worse(vpii &A, long long val) {
   //  return;
   while (!A.empty() && A.back().st >= val) {
      A.pop_back();
   }
}

// bool okolo(double a, double b) { return 0.2 <= a / b && a / b <= 5.0; }

mpii combine(mpii &A, mpii &B, int val) {
   mpii M(sz(A) + sz(B) - 1);

   for (int i = 0; i < sz(A); i++)
      for (int j = 0; j < sz(B); j++)
         //  if ((i <= 2 && j <= 2) || i == 0 || j == 0 || okolo((long double)rA / i, (long double)rB / j))
         combine(A[i], B[j], M[i + j], val, i + j, M);

   // debug("mapa przed", res);

   for (auto &r : M)
      r = normalize(r);

   // debug("mapa", res);
   return M;
}

long long best(vpii &A) {
   long long res = inf;
   for (auto a : A)
      res = min(res, a.st + (long long)a.nd * (long long)a.nd);
   return res;
}

int get_size(mpii M) {
   int s = 0;
   for (auto m : M)
      s += m.size();
   return s;
}

mpii dfs(int x, int p = -1) {

   sum[x] = val[x];
   rozmiar_poddrzewa[x] = 1;
   mpii M(1);
   M[0].push_back({0, val[x]});

   for (int y : G[x])
      if (y != p) {
         auto T = dfs(y, x);
         sum[x] += sum[y];
         rozmiar_poddrzewa[x] += rozmiar_poddrzewa[y];
         M = combine(M, T, sum[x]);
         // remove_big(M, sum[x]);
      }

   // remove_big(M, sum[x]);

   M.resize(rozmiar_poddrzewa[x] + 1);

   for (int i = rozmiar_poddrzewa[x] - 1; i >= 0; i--) {
      long long a = best(M[i]);
      if (a == inf)
         continue;
      remove_worse(M[i + 1], a);
      M[i + 1].push_back({a, 0});
   }
   // debug(x, M, get_size(M));
   return M;
}

int32_t main() {
   int Z;
   cin >> Z;
   while (Z--) {
      pre();
      // long long S = accumulate(val, val + n, 0ll);
      //  debug(S);

      pii x = {9, 9};
      rep(i, n) x = min(x, {sz(G[i]), i});
      auto M = dfs(x.nd);
      for (int i = 1; i <= n; i++)
         cout << best(M[i - 1]) << " ";

      cout << endl;
      // long long najlepszy = 0;
      // rep(i, n) najlepszy += (long long)val[i] * val[i];
      // long long worst = S * S;
      // debug(najlepszy, worst);
      // assert(najlepszy <= best(M[n - 1]));
      // debug(ile);
   }
}