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
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
const int INF = 0x3f3f3f3f;

#define FOR(i,b,e) for(int i = (b); i < (e); i++)
#define TRAV(x,a) for(auto &x: (a))
#define SZ(x) ((int)x.size())
#define PB push_back
#define X first
#define Y second

const int N = 305;

int n;
int val[N], rozm[N];
vector<pair<ll, ll>> dp[N][N];
vi G[N];

ll obl(pair<ll, ll> &v){
    return v.X + v.Y*v.Y;
}

void dfs(int v, int p){
    dp[v][0] = {{0, val[v]}};
    rozm[v] = 1;
    TRAV(u, G[v]){
        if(u == p) continue;
        dfs(u, v);
        rozm[v] += rozm[u];
    }
    TRAV(u, G[v]){
        if(u == p) continue;
        for(int k = rozm[v]-1; k >= 0; k--){
            vector<pair<ll, ll>> nowe;
            FOR(i, 0, k+1){
                TRAV(el1, dp[v][i]){
                    TRAV(el2, dp[u][k-i]){
                        nowe.PB({el1.X+el2.X, el1.Y+el2.Y});
                    }
                    if(k-i-1 < 0) continue;
                    TRAV(el2, dp[u][k-i-1]){
                        nowe.PB({el1.X+el2.X+el2.Y*el2.Y, el1.Y});
                    }
                }
            }
            sort(nowe.begin(), nowe.end());
            dp[v][k].clear();
            TRAV(x, nowe){
                if(SZ(dp[v][k]) == 0 || x.Y < dp[v][k].back().Y) dp[v][k].PB(x);
            }
            nowe.clear();
            ll mink = 1ll*INF*INF;
            for(int i = SZ(dp[v][k])-1; i >= 0; i--){
                if(obl(dp[v][k][i]) < mink) nowe.PB(dp[v][k][i]);
                mink = min(mink, obl(dp[v][k][i]));
            }
            dp[v][k] = nowe;
        }
    }
}

ll wart(int k){
    ll ret = 1ll*INF*INF;
    TRAV(x, dp[0][k]) ret = min(ret, obl(x));
    return ret;
}

void solve(){
    cin >> n;
    FOR(i, 0, n) cin >> val[i];
    FOR(i, 1, n){
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].PB(b);
        G[b].PB(a);
    }
    dfs(0, 0);
    FOR(i, 0, n) cout << wart(i) << ' ';
    cout << '\n';
    FOR(i, 0, n) G[i].clear();
    FOR(i, 0, n) FOR(k, 0, rozm[i]) dp[i][k].clear();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt; cin >> tt;
    FOR(te, 0, tt)
    solve();
    return 0;
}