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
#include <bits/stdc++.h>
using namespace std;

long long W[50];//Wynik
short B[50];//Mapa miasta
pair<short, short>Zakaz[50];//Zakazane polaczenia
long long T[50];//Wartosc miast
short n;//Ile miast
short t;
int k;

long long Licz(vector<short>A[], bool B[], short k)
{
    long long wynik=0;
    B[k]=true;
    wynik+=T[k];

    for (int i=0; i<A[k].size(); ++i)
        if (B[A[k][i]]==false)
            wynik+=Licz(A, B, A[k][i]);

    return wynik;
}

long long Find()
{
    long long wynik=0;
    vector<short>G[50];
    bool Meet[50];

    for (short i=0; i<n; ++i)
        Meet[i]=false;

    for (short i=0; i<n-1; ++i)
        if (B[i]==0){
            G[Zakaz[i].first-1].push_back(Zakaz[i].second-1);
            G[Zakaz[i].second-1].push_back(Zakaz[i].first-1);
        }

    for (short i=0; i<n; ++i)
        if (Meet[i]==false){
            long long x=Licz(G, Meet, i);
            wynik+=(x*x);
        }
    return wynik;
}

void Upp(int A)//Zwiekszanie bitow
{
    if (B[A]==0){
        B[A]=1;
        return;
    }
    else{
        B[A]=0;
        Upp(A+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>t;
    while (t>0){

        cin>>n;

        k=1;
        for (int i=1; i<=n-1; ++i)
            k=k*2;

        for (short i=0; i<n; ++i)//Zeruj wartosc miast
            cin>>T[i];

        for (short i=0; i<n-1; ++i)//Wpisz zakazane drogi
            cin>>Zakaz[i].first>>Zakaz[i].second;

        for (short i=0; i<50; ++i)//Zeruj bity
            B[i]=0;

        for (short i=1; i<50; ++i)//Zeruj wyniki
            W[i]=1000000000000000018;

        for (int i=0; i<k; ++i){//Sprawdz na pale

            short ile=0;
            for (short j=0; j<n-1; ++j)
                if (B[j]==1)
                    ++ile;

            W[ile]=min(W[ile], Find());//Znajdz wynik
            Upp(0);
        }

        long long xa=0;
        for (int i=0; i<n; ++i)
            xa+=T[i];
        cout<<xa*xa<<" ";

        for (short i=1; i<n; ++i)
            cout<<W[i]<<" ";
        cout<<"\n";


        --t;
    }

    return 0;
}