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
115
116
117
118
119
//Marcin Wróbel
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,x,y) for(int i = (int)(x); i < (int)(y); ++i)
#define FORE(i,x,y) for(int i = (int)(x); i <= (int)(y); ++i)
#define FORD(i,x,y) for(int i = (int)(x); i >= (int)(y); --i)
#define PB push_back
#define ST first
#define ND second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MAXN=307;
const ll INFLL = 1e18;

int t,n;
int a[MAXN];
int d[MAXN];
vector<int> e[MAXN];
int nxte[MAXN];
int V[MAXN];
int cof[MAXN];
ll ccVal[MAXN];
mt19937 rnd(123);

int CmpS(const int i) {return rnd()%i;}
class Cmp{
    public:
    inline bool operator() (const int &p1,const int &p2) const {
        return d[p1] > d[p2];
    }
};
class CmpQ{
public:
    bool operator() (const pii &p1,const pii &p2) const {
        return p1.ST > p2.ST;
    }
};

ll Proba(int k) {

    FORE(i,1,n) {
        cof[i] =0;
        nxte[i]=0;
    }
    priority_queue<pii,vector<pii>,CmpQ> Q;
    FORE(i,1,k){
        cof[V[i]]=i;
        ccVal[i]=a[V[i]];
        Q.push({(ccVal[i] * (90 + rnd()%21))/100,V[i]});
    }
    while(!Q.empty()) {
        pii w = Q.top();Q.pop();
        int v = w.ND;
        for (;nxte[v]<e[v].size();++nxte[v]) {
            int w = e[v][nxte[v]];
            if (cof[w] != 0) continue;
            ccVal[cof[v]] += a[w];
            cof[w] = cof[v];
            Q.push({(ccVal[cof[w]]* (90 + rnd()%21))/100,w});
            break;
        }
        if (nxte[v]<e[v].size())Q.push({(ccVal[cof[v]] * (90 + rnd()%21))/100,v});
    }

    ll ans=0;
    FORE(i,1,k) {
        ans+=(ccVal[i]*ccVal[i]);
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        ll res[MAXN];
        res[0] = 0;
        FORE(i,1,n) {
            cin>>a[i];
            e[i].clear();
            res[i] = INFLL;
            V[i] = i;
        }
        FOR(i,1,n) {
            int v,w;
            cin>>v>>w;
            e[v].PB(w);
            e[w].PB(v);
        }
        int mxi =1700/n;
        if (n <= 100) mxi *=3;
        if (n <= 20) mxi*=5;
        FORE(j,1,mxi){
            FORE(i,1,n) {
                random_shuffle(e[i].begin(),e[i].end(),CmpS);
                d[i] = a[i] * (10 + rnd()%181);
                d[i] /= 100;
            }
            sort(V+1,V+n+1,Cmp());
            FORE(i,1,n) {
                res[i] = min(res[i],Proba(i));
            }
        }
        FORE(i,1,n) cout<<res[i]<<" ";
        cout<<"\n";
    }
    return 0;
}
/*
1
5
4 8 2 3 1
4 3
3 1
4 2
5 1
*/