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

using namespace std;

#define f first
#define s second

const int MAXN = 313;
const long long INF = 1e18 + 3;

int r[MAXN];
int odw[MAXN];
int zab[MAXN];
int kol[MAXN];
long long w[MAXN];
long long ans[MAXN];
vector<pair<int, int> > v[MAXN];
vector<pair<int, int> > v2[MAXN];
long long temp;
int tm, cnt;

void preDFS(int x, int oj) {
    kol[++tm] = x;
    for (auto it:v2[x]) {
        if (it.f != oj) {
            v[x].push_back(it);
            preDFS(it.f, x);
        }
    }
}

void DFS(int x) {
    temp += w[x];
    odw[x] = cnt;
    for (auto it:v[x]) {
        if (zab[it.s] != cnt)
            DFS(it.f);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int z, n;
    long long wyn;
    int x, y, mx, ile, licz;
    cin >> z;
    while (z--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            r[i] = odw[i] = zab[i] = kol[i] = 0;
            v2[i].clear();
            v[i].clear();
            ans[i] = INF;
        }
        cnt = tm = 0;
        for (int i = 1; i <= n; i++)
            cin >> w[i];
        for (int i = 1; i < n; i++) {
            cin >> x >> y;
            v2[x].emplace_back(y, i);
            v2[y].emplace_back(x, i);
        }
        preDFS(1, 0);
        mx = 1 << (n - 1);
        for (int i = 0; i < mx; i++) {
            x = i;
            cnt++;
            licz = 0;
            ile = 1;
            wyn = 0;
            while (x) {
                licz++;
                if (x & 1) {
                    ile++;
                    zab[licz] = cnt;
                }
                x >>= 1;
            }
            for (int j = 1; j <= n; j++) {
                if (odw[kol[j]] != cnt) {
                    temp = 0;
                    DFS(kol[j]);
                    wyn += temp * temp;
                }
            }
            ans[ile] = min(ans[ile], wyn);
        }
        for (int i = 1; i <= n; i++)
            cout << ans[i] << ' ';
        cout << '\n';
    }
    return 0;
}