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

typedef unsigned long long ull;

struct kr
{
    int u, nr;
};

int t, ls[305], val[305], wyw, us[305];
ull wyn;

ull dfs(int v, int oj, bool co, vector <kr>* gr)
{
    ull sum = ull(val[v]);

    for(auto& i : gr[v])
    {
        int u = i.u, nr = i.nr;

        if(u ^ oj)
            sum += dfs(u, v, bool(us[nr] == wyw), gr);
    }

    if(co == 0)
        return sum;

    wyn += sum * sum;

    return ull(0);
}

void solve()
{
    int n;
    vector <kr> gr[301];

    scanf("%d", &n);

    for(int i = 1; i <= n; i++)
        scanf("%d", &val[i]);

    for(int i = 0; i < n - 1; i++)
    {
        int a, b;

        scanf("%d%d", &a, &b);

        gr[a].push_back({b, i});
        gr[b].push_back({a, i});
    }

    for(int i = 0; i < n - 1; i++)
        ls[i] = i;

    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();

    if(n > 2)
        shuffle(ls, ls + n - 2, default_random_engine(seed));

    for(int k = 0; k < n; k++)
    {
        int zl = 0;
        ull wync = ULLONG_MAX;

        for(int qu = 0; qu < 700; qu++)
        {
            wyw++;

            for(int i = 1; i <= k; i++)
            {
                int tym = rand() % (n - i);

                us[ls[tym]] = wyw;

                swap(ls[tym], ls[n - i - 1]);
            }

            wyn = ull(0);
            ull ig = dfs(1, 0, 1, gr), tym = wync;

            wync = min(wync, wyn);

            if(wync == tym)
                zl++;
            else
                zl = 0;

            if((k < n / 4 || 3 * n / 4 < k) && zl > 100)
                break;
        }

        printf("%llu ", wync);
    }

    printf("\n");
}

int main()
{
    scanf("%d", &t);

    for(int qu = 0; qu < t; qu++)
        solve();
}