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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;


long long a[512];
long long ile[512];
int vis[512];

const long long INF = 1e18;

vector<int> v[512];
set<pair<int, int>> S;

long long dfs(int u)
{
  vis[u] = 1;
  
  long long ret = a[u];
  for (int i = 0; i < v[u].size(); i++)
  {
    int v1 = v[u][i];
    if (!vis[v1] && S.find({u, v1}) == S.end())
    {
      //printf("%d %d\n", u, v1);
      ret += dfs(v1);
    }
  }
  return ret;
}

int main()
{
  int t;
  scanf("%d", &t);
  
  while (t--)
  {
    int n;
    scanf("%d", &n);
    
    S.clear();
    
    for (int i = 0; i < n; i++)
    {
      scanf("%lld", a + i);
      ile[i] = INF;
    }
    vector<pair<int, int>> edges;
    for (int i = 0; i < n - 1; i++)
    {
      int x, y;
      scanf("%d %d", &x, &y);
      --x, --y;
      v[x].push_back(y);
      v[y].push_back(x);
      edges.push_back({x, y});
      edges.push_back({y, x});
    }
    
    for (int i = 0; i < (1 << (n - 1)); i++)
    {
      long long ret = 0;
      
      int ile_b = 0;
      S.clear();
      for (int j = 0; j < n - 1; j++)
      {
        if (i & (1 << j))
        {
          S.insert(edges[2 * j]);
          S.insert(edges[2 * j + 1]);
          ile_b++;
        }
      }
      memset(vis, 0, sizeof(vis));
      for (int j = 0; j < n; j++)
      {
        if (!vis[j])
        {
          long long r = dfs(j);
          ret += r * r;
        }
      }
      ile[ile_b] = min(ile[ile_b], ret);
    }
    
    for (int i = 0; i < n; i++)
    {
      printf("%lld ", ile[i]);
    }
    printf("\n");
    
    for (int i = 0; i < n; i++)
    {
      v[i].clear();
    }
  }
  
  
  
  return 0;
}