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
#include <bits/stdc++.h>
using namespace std;
const int MX=305;
int t,n,cnt,w,i,X,Y,st,x[MX],y[MX],a[MX],p[MX],rk[MX];
long long tm_beg,best,tot,sum,sz[MX],res[MX];
vector<int> g[MX];
bool ok[MX];
void dfs(int i, int pe, int w) {
  p[i]=w;
  rk[i]=1;
  sz[w]+=a[i];
  for (int j: g[i]) if (j!=pe) {
    int k=x[j]+y[j]-i;
    dfs(k,j,(ok[j]?k:w));
  }
}
int fs(int x) {
  if (x!=p[x]) p[x]=fs(p[x]);
  return p[x];
}
void un(int x, int y) {
  if (rk[x]>rk[y]) {
    p[y]=x;
    sz[x]+=sz[y];
  } else {
    p[x]=y;
    sz[y]+=sz[x];
    if (rk[x]==rk[y]) ++rk[y];
  }
}
int main() {
  tm_beg=chrono::steady_clock::now().time_since_epoch().count();
  mt19937_64 rng(tm_beg);
  scanf("%d",&t);
  while (t--) {
    scanf("%d",&n);
    tot=sum=0;
    for (i=1; i<=n; i++) {
      scanf("%d",&a[i]);
      g[i].clear();
      p[i]=i;
      rk[i]=1;
      sz[i]=a[i];
      sum+=sz[i];
      tot+=sz[i]*sz[i];
    }
    for (i=1; i<n; i++) {
      scanf("%d%d",&x[i],&y[i]);
      g[x[i]].push_back(i);
      g[y[i]].push_back(i);
      ok[i]=true;
    }
    sum*=sum;
    for (cnt=i=0; i<n; i++) res[i]=i?sum:tot;
    st=0;
    while (true) {
      while (cnt<n-1) {
        best=w=0;
        for (i=1; i<n; i++) if (ok[i]) {
          X=fs(x[i]);
          Y=fs(y[i]);
          if (X!=Y && (w==0 || sz[X]*sz[Y]<best)) { best=sz[X]*sz[Y]; w=i; }
        }
        ok[w]=false;
        un(fs(x[w]),fs(y[w]));
        tot+=2*best;
        if (tot<res[++cnt]) {
          res[cnt]=tot;
          st=0;
        }
      }
      //for (i=0; i<n; i++) printf("%lld ~%c",res[n-1-i],(i==n-1)?'\n':' ');
      ++st;
      if (st>=n) break;
      for (i=1; i<=st; i++) {
        int num=rng()%(n-i);
        for (int j=1; j<n; j++) if (!ok[j]) {
          --num;
          if (num<0) {
            ok[j]=true;
            break;
          }
        }
      }
      cnt-=st;
      for (i=1; i<=n; i++) sz[i]=0;
      dfs(1,0,1);
      tot=0;
      for (i=1; i<=n; i++) if (fs(i)==i) tot+=sz[i]*sz[i];
    }
    for (i=0; i<n; i++) printf("%lld%c",res[n-1-i],(i==n-1)?'\n':' ');
  }
  return 0;
}