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

using namespace std;

const int MAX_N = 307;
const long long inf = ((long long)1) << 62;

vector<int>adj[MAX_N];
long long a[MAX_N];
int parent[MAX_N], visited[MAX_N], n, t;
void ReadData(), PreDFS(int x, int p);
long long GetMin(int index, int current, int maxAmount), Check(), DFS(int x);

int main() {
    ios_base::sync_with_stdio(0);
    cin >> t;
    while(t--) {
        ReadData();
        PreDFS(0, -1);
        for(int i = 0; i < n; i++)
            cout << GetMin(1, 0, i) << ' ';
        cout << '\n';
    }
    return 0;
}

long long GetMin(int index, int current, int maxAmount) {
    if(index == n)
        return Check();
    long long result = inf;
    if(current < maxAmount) {
        visited[index] = 2;
        result = GetMin(index + 1, current + 1, maxAmount);
    }
    if(n - index > maxAmount - current) {
        visited[index] = 0;     
        result = min(result, GetMin(index + 1, current, maxAmount));
    }
    return result;
}

long long Check() {
    long long result = 0;
    visited[0] = 2;
    for(int i = 1; i < n; i++)
        if(visited[i] != 2)
            visited[i] = 0;
    for(int i = 0; i < n; i++) {
        if(visited[i] == 2) {
            long long temp = DFS(i);
            result += temp * temp;
        }
    }
    return result;
}

long long DFS(int x) {
    if(visited[x] != 2)
        visited[x] = 1;
    long long result = a[x];
    for(int y : adj[x])
        if(visited[y] == 0 && y != parent[x])
            result += DFS(y);
    return result;
}

void PreDFS(int x, int p) {
    visited[x] = 1;
    parent[x] = p;
    for(int y : adj[x])
        if(!visited[y])
            PreDFS(y, x);
}

void ReadData() {
    int x, y;
    cin >> n; 
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        adj[i].clear();
        visited[i] = false;
    }
    for(int i = 1; i < n; i++) {
        cin >> x >> y;
        adj[x - 1].push_back(y - 1);
        adj[y - 1].push_back(x - 1);
    }
}

/*
2 
7
9 1 4 2 6 4 7
1 7
6 4
2 3
5 7
3 4
5 3
5
4 8 2 3 1
4 3
3 1
4 2
5 1
*/