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 <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <cstdlib>
#include <random>
#include <climits>
using namespace std;
void input(long long &n, vector<vector<long long>> &G, deque<pair<long long, long long>> &sortedG,
           vector<long long> &cost, long long &sum) {
  long long x, a, b;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x;
    cost.push_back(x);
    sortedG.push_back({-x, i});
    sum += x;
  }
  sort(begin(sortedG), end(sortedG));
  G.resize(n);
  for(int i = 0; i < n - 1; i++) {
    cin >> a >> b;
    G[a - 1].push_back(b - 1);
    G[b - 1].push_back(a - 1);
  }
}
pair<long long, long long> dfs(vector<vector<long long>> &G, vector<long long> &cost,
                   long long x, long long parent, long long maks, long long &result, long long &sum) {
  if (cost[x] > maks) return {0, LLONG_MAX};
  if (cost[x] == 0) return {0, 0};
	vector<pair<long long, long long>> children;
	for (long long child : G[x]) {
		if (child != parent) {
      children.push_back(dfs(G, cost, child, x, maks, result, sum));
    }
	}
	sort(begin(children), end(children));
  long long ovrsize = cost[x], ovrremoved = 0;
	for (auto [size, removed] : children) {
    if (ovrsize + size <= maks) ovrsize += size;
		else {
      result += (size * size);
      sum -= size;
      ovrremoved++;
    }
		ovrremoved += removed;
	}
	return {ovrsize, ovrremoved};
}
void solve(vector<vector<long long>> G, vector<long long> cost, deque<pair<long long, long long>> sortedG,
          long long k, long long new_sum, long long wtf, long long &best_res, bool change, long long guess) {
  if (change) {
    cost[sortedG[guess].second] = 0;
    new_sum += sortedG[guess].first;
    wtf += (sortedG[guess].first * sortedG[guess].first);
    sortedG.erase(sortedG.begin() + guess);
  }
  sort(begin(sortedG), end(sortedG));
  for (int start = 0; start < sortedG.size(); start++) {
    if (cost[sortedG[start].second] == 0) continue;
    long long left = 1, right = LLONG_MAX, mid;
    while (left <= right) {
      mid = left + ((right - left) / 2);
      long long res = 0, sum_ = new_sum;
      long long val = dfs(G, cost, sortedG[start].second, -1, mid, res, sum_).second;
      if (val >= k || val < 0) left = mid + 1;
      else right = mid - 1;
    }
    long long result = 0, sum_ = new_sum;
    long long counter = dfs(G, cost, sortedG[start].second, -1, right + 1, result, sum_).second + 1;
    if (sum_ > right + 1) return;
    best_res = min(best_res, result + wtf + (sum_ * sum_));
    if (counter < k) {
      if (-sortedG[0].first == right + 1) {
        solve(G, cost, sortedG, k - 1, new_sum, wtf, best_res, true, 0);
      }
      else {
        for (long long i = 0; i < sortedG.size(); i++) {
          if (cost[sortedG[i].second] != 0) {
            solve(G, cost, sortedG, k - 1, new_sum, wtf, best_res, true, i);
          }
        }
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  long long t;
  cin >> t;
  while (t--) {
  	long long n, u, v, sum = 0;
    vector<vector<long long>> G;
    vector<long long> cost_;
    deque<pair<long long, long long>> sortedG_;
    input(n, G, sortedG_, cost_, sum);
    for (int k = 1; k <= n; k++) {
      vector<long long> cost = cost_;
      deque<pair<long long, long long>> sortedG = sortedG_;
      long long counter = 0, result, sum_, new_sum = sum, wtf = 0, best_res = LLONG_MAX;
      solve(G, cost, sortedG, k, new_sum, wtf, best_res, false, 0);
      cout << best_res << " ";
    }
    cout << "\n";
  }
  return 0;
}