#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(a) begin(a),end(a)
#define FOR(x,val,to) for(int x=(val);x<int((to));++x)
#define FORE(x,val,to) for(auto x=(val);x<=(to);++x)
#define FORR(x,arr) for(auto &x: arr)
#define FORS(x,plus,arr) for(auto x = begin(arr)+(plus); x != end(arr); ++x)
#define FORREV(x,plus,arr) for(auto x = (arr).rbegin()+(plus); x !=(arr).rend(); ++x)
#define REE(s_) {cout<<s_<<'\n';exit(0);}
#define GET(arr) for(auto &i: (arr)) sc(i)
#define whatis(x) cerr << #x << " is " << (x) << endl;
#define e1 first
#define e2 second
#define INF 0x7f7f7f7f
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
typedef std::vector<std::string> vs;
typedef int64_t ll;
typedef uint64_t ull;
#define umap unordered_map
#define uset unordered_set
using namespace std;
using namespace __gnu_pbds;

#ifdef ONLINE_JUDGE
#define whatis(x) ;
#endif
#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
template<class L, class R> ostream& operator<<(ostream &os, map<L, R> P) { for(auto const &vv: P)os<<"("<<vv.first<<","<<vv.second<<")"; return os; }
template<class T> ostream& operator<<(ostream &os, set<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class T> ostream& operator<<(ostream &os, multiset<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class T> ostream& operator<<(ostream &os, vector<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class L, class R> ostream& operator<<(ostream &os, pair<L, R> P) { os<<"("<<P.first<<","<<P.second<<")"; return os; }
inline int fstoi(const string &str){auto it=str.begin();bool neg=0;int num=0;if(*it=='-')neg=1;else num=*it-'0';++it;while(it<str.end()) num=num*10+(*it++-'0');if(neg)num*=-1;return num;}
inline void getch(char &x){while(x = getchar_unlocked(), x < 33){;}}
inline void getstr(string &str){str.clear(); char cur;while(cur=getchar_unlocked(),cur<33){;}while(cur>32){str+=cur;cur=getchar_unlocked();}}
template<typename T> inline bool sc(T &num){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){if(c == EOF) return false;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; return true;}template<typename T, typename ...Args> inline void sc(T &num, Args &...args){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; sc(args...); }
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //s.find_by_order(), s.order_of_key() <- works like lower_bound
template<typename T> using ordered_map = tree<T, int, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 307

// WTFFFFFFFFFFFFFFFFFFFFFFFFFFF
// 30 godzin klepania
// 0 snu
// 6 stron a4
// 700 linijek kodu
// ...later
// -> przechodzi test Zyzika wtf

// Może jak dodam convex hull trick w losowe miejsce to zacznie działać
// -> XD

const ll is_qu = -(1ll << 61);

struct Line{
    ll m,b;
    //pamiętać trzeba mutable i <const Line*()>
    mutable function<const Line*()> succ; //aby w comparatorze mieć dostęp do nexta Linii
    bool operator < (const Line &rhs) const{
        if(rhs.b != is_qu){ //hackish - gdy porównujemy przy insercie liczy się tylko m
            return m < rhs.m;
        }
        //przy lower boundzie - porównujemy z nextem dla danego iksa
        const Line *nx = succ();
        if(!nx) return 0;
        ll x = rhs.m;
        //overflow v2??
        //no dif:c
        //nie no, tu nie może być
        return x*m+b < x*nx->m+nx->b;
        /* return (double)x*m+b < (double)x*nx->m+nx->b; */
    }
};
ostream& operator<<(ostream &os, Line L) { os<<"("<<L.m<<","<<L.b<<")"; return os; }

//inherituje od multisetu, to istotne!
//multiset nie set (idk czemu, ale tak ma być)
struct hull : public multiset<Line>{
    bool bad(iterator y){
        auto nx = next(y);
        if(y == begin()){
            if(nx == end()) return 0;
            return y->m == nx->m && y->b <= nx->b;
        }
        auto pr = prev(y);
        if(nx == end()){
            return y->m == pr->m && y->b <= pr->b;
        }
        //to cza pamiętać, zawsze najpierw m i b, w 1. najpierw nx potem pr,
        //potem na odwrót i na odwrót kolejność z y
        //double żeby overflowu nie było
        //epsilon???
        return (double)(nx->m-y->m)*(pr->b-y->b) >= (double)(y->m-pr->m)*(y->b-nx->b);
        // ???? jak to się nie syfi
        /* return ((double)(nx->m-y->m)*(pr->b-y->b) - (double)(y->m-pr->m)*(y->b-nx->b)) > -10; */
        /* return (double)(nx->m-y->m)*(pr->b-y->b) > (double)(y->m-pr->m)*(y->b-nx->b); */
        //może modyfikacja, i nie wywalanie równych??
        //co jak równe wsm?
        /* return (long double)(nx->m-y->m)*(pr->b-y->b) >= (long double)(y->m-pr->m)*(y->b-nx->b); */
    }
    void insert_line(ll m, ll b){
        /* whatis(m) */
        /* whatis(b) */
        auto y = insert({m,b});
        // [=]
        y->succ = [=]{return next(y) == end() ? 0 : &*next(y);}; //referencja nie iterator
        if(bad(y)){
            erase(y);
            return;
        }
        while(y != begin() && bad(prev(y))){
            erase(prev(y));
        }
        while(next(y) != end() && bad(next(y))){
            erase(next(y));
        }
    }
    ll eval(ll x){
        auto l = *lower_bound((Line){x,is_qu});
        return l.m*x+l.b;
    }
    Line eval_raw(ll x){
        /* whatis(x) */
        auto l = *lower_bound((Line){x,is_qu});
        // return equal_range??
        return l;
    }
    // syf
    auto eval_raw_many(ll x){
        /* whatis(x) */
        auto l = lower_bound((Line){x,is_qu});
        vector<Line> ret = {*l};
        // return equal_range??
        for(;;){
            /* const Line *nx = l->succ(); */
            const Line *nx = ret.back().succ();
            if(!nx) return ret;
            //overflow v2??
            //no dif:c
            //epsilon?
            if(x*ret.back().m+ret.back().m != x*nx->m+nx->b)
                return ret;
            ret.pb(*nx);
        }
    }
    void reset_succ(){
        for(auto y = begin(); y != end(); ++y){
            y->succ = [=]{return next(y) == end() ? 0 : &*next(y);}; //referencja nie iterator
        }
    }
};

// nie moge clearowac, bo jakis deallocator sie wtedy robi, a ja mam te
// wskaźniki stale ustawione dla succ
// chyba że co copy, sam przejdę po all nodach, i zaś ustawaię y->succ ponownie?
// let's try that

// eval(x) -> Get maximum value of ax+b on all inserted lines
// min = -eval(x) on -a -b
// or -eval(-x) on a -b

vi adj[N];
/* int val[N]; */
ll val[N];
// prob list / vector better
/* set<pair<ll,ll>> dp[N][N]; // [node][ile_krawedz_usunietych] -> {res_poza_obecna, obecna_suma} */
vector<pair<ll,ll>> dp[N][N]; // [node][ile_krawedz_usunietych] -> {res_poza_obecna, obecna_suma}
// też po prostu min i.first + i.second * i.second, na potrzeby gdy chcemy remować edge z parentem
ll dprem[N][N]; // -> 1 clean optimal state

hull dphull[N][N]; // pls work

// jak mam convex hull trick, to nie muszę manualnie robić tych czystek btw

/* void rec(int it, int , int k){ */
/* } */

ll szsum[N];
int nn;

// średnio mała wysokość (max logn z sensownym prawdopodobieństwem)
void d1(int v, int p){
    /* vi adj2; */
    FORR(i,adj[v]){
        if(i == p)
            continue;
        d1(i,v);
        /* adj2.push_back(i); // dla prostoty */
    }
    // base case jak leafem jest jeszcze duh
    /* if(~p && adj[v].size() == 1){ */
    /*     dp[v][0].insert({0,val[v]}); */
    /*     return; */
    /* } */
    // not needed wsm (although can be faster prob)
    // średnio mały deg (max logn z sensownym prawdopodobieństwem)
    // lambda może być wolniejsza
    // globalnie mogę te rzeczy wsm trzymać i modyfikować

    /* function<void(vi::iterator, int, ll, ll)> rec = [&](vi::iterator it, int k, ll cres, ll csum) -> void{ */
    /*     if(it == adj[v].end()){ */
    /*         /1* dp[v][k].insert({cres,csum}); *1/ */
    /*         /1* dp[v][k].insert({cres,csum + val[v]}); *1/ */
    /*         // *zachowanie monotonizmu* -> lepiej od razu, czy potem posortować */
    /*         // i to ogarnąć? */
    /*         // ponieważ od zera to setuppuję, to wsm znacznie lepiej wektory */
    /*         // mieć od setów, sortować i potem ogarniać */
    /*         /1* dp[v][k].insert({cres,csum}); *1/ */
    /*         dp[v][k].push_back({cres,csum}); */
    /*         return; */
    /*     } */
    /*     if(*it == p){ */
    /*         rec(it + 1, k, cres, csum); */
    /*         return; */
    /*     } */
    /*     // any child used-up k up till limit; whether will erase edge */
    /*     // dla różnych k ma też różne staty btw -> podwójna pętla w reku damn */
    /*     for(int crk = 0; !dp[*it][crk].empty(); ++crk){ */
    /*         FORR(i,dp[*it][crk]){ */
    /*             // bez usuwania direct edgea */
    /*             rec(it + 1, k + crk, cres + i.first, csum + i.second); */
    /*             // z usuwaniem direct edgea */
    /*             rec(it + 1, k + crk + 1, cres + i.first + i.second * i.second, csum); */
    /*         } */
    /*     } */
    /* }; */

    // giga taktyk z niewyłowywaniem tego
    // "niewyłowywaniem" hmm
    // *niewywoływaniem
    // Peczarski by wyzerował projekt
    /* rec(adj[v].begin(), 0, 0, 0); */
    /* rec(adj[v].begin(), 0, 0, val[v]); */
    // aż not empty w teorii, ale to mikroopt anyway
    // ale why not i guess

    // najs, ale lepiej na każdym przerobionym prefiksie wywalać nieoptymalne
    // -> iteracyjnie możemy to robić, trzymając staty na prev i next (czy tam
    // cur) prefiksie

    /* for(int crk = 0; !dp[v][crk].empty(); ++crk){ */
    /*     sort(all(dp[v][crk])); */
    /*     vector<pair<ll,ll>> tmp; // easier much */
    /*     // mogę tryhardować stałym stackiem */
    /*     for(int i = 0; i < dp[v][crk].size(); ++i){ */
    /*         if(tmp.empty() || tmp.back().e2 > dp[v][crk][i].e2) */
    /*             tmp.push_back(dp[v][crk][i]); */
    /*     } */
    /*     whatis(dp[v][crk].size()) */
    /*     whatis(tmp.size()) */
    /*     whatis(dp[v][crk].size() - tmp.size()) */
    /*     dp[v][crk] = tmp; */
    /* } */

    /* vector<pair<ll,ll>> crdp[nn]; // od maxk // w teorii == subtree cnt ale whatever */
    /* vector<pair<ll,ll>> nxdp[nn]; */
    /* crdp[0].push_back({0, val[v]}); */
    /* dphull[v][0].insert_line(0,0); */
    hull crdphull[nn];
    hull nxdphull[nn];
    // i.first, i.second -> (i.second, -(i.first + i.second^2))
    // -> -query od -2x.second
    crdphull[0].insert_line(val[v], -(val[v] * val[v]));

    /* FORR(i,adj2){ // bez preva */
    // not needed wsm
    /* whatis(v) */
    // can this change anything?
    /* sort(all(adj[v]),[&](int f, int s){return szsum[f] < szsum[s];}); */
    /* sort(all(adj[v]),[&](int f, int s){return szsum[f] > szsum[s];}); */
    // -> nope, no dif whatsoever

    // iteracje po multisetach slow much?
    FORR(i,adj[v]){
        if(i == p)
            continue;
        for(int k = 0; !crdphull[k].empty(); ++k){
            /* whatis(crdphull[k]) */
            FORR(x,crdphull[k]){
                /* whatis(x) */
                /* whatis(k) */
                Line normx = {x.m,-x.b};
                for(int crk = 0; !dphull[i][crk].empty(); ++crk){
                    // actually, let's not pick one line, let's try it na pałe
                    // jak wcześniej; może po prostu to większą czystke robi
                    // niż po zwykłym sorcie i wywalaniach jak e2 >= prev(e2),
                    // bo to jest sprytniejszy convex hull.
                    // Dziwne że wcześniej tego nie spróbowałem wsm
                    /* whatis(k+crk) */

                    /* auto best = dphull[i][crk].eval_raw(-2*x.m); */
                    /* Line normi = {best.m,-best.b}; */
                    /* /1* nxdphull[k + crk].insert_line(best.m + x.m, -(-best.b -x.b + best.m * best.m + x.m * x.m)); // na minusie both *1/ */
                    /* nxdphull[k + crk].insert_line(normi.m + normx.m, -(normi.b - normi.m * normi.m + normx.b - normx.m * normx.m + (normi.m + normx.m) * (normi.m + normx.m))); */
                    /* whatis(normi) */
                    /* whatis(Line({normi.m + normx.m, -(normi.b - normi.m * normi.m + normx.b - normx.m * normx.m + (normi.m + normx.m) * (normi.m + normx.m))})) */
                    FORR(j,dphull[i][crk]){
                        // bez usuwania direct edgea
                        /* rec(it + 1, k + crk, cres + i.first, csum + i.second); */
                        Line normi = {j.m,-j.b};
                        /* nxdp[k + crk].push_back({x.first + j.first, x.second + j.second}); */
                        nxdphull[k + crk].insert_line(normi.m + normx.m, -(normi.b - normi.m * normi.m + normx.b - normx.m * normx.m + (normi.m + normx.m) * (normi.m + normx.m)));
                        // z usuwaniem direct edgea
                        /* nxdp[k + crk + 1].push_back({x.first + j.first + j.second * j.second, x.second}); */
                        /* rec(it + 1, k + crk + 1, cres + i.first + i.second * i.second, csum); */
                    }
                    /* auto bests = dphull[i][crk].eval_raw_many(-2*x.m); */
                    /* /1* whatis(bests.size()) *1/ */
                    /* assert(bests.size() == 1); */
                    /* FORR(normi,bests){ */
                    /*     normi.b *= -1; */
                    /*     nxdphull[k + crk].insert_line(normi.m + normx.m, -(normi.b - normi.m * normi.m + normx.b - normx.m * normx.m + (normi.m + normx.m) * (normi.m + normx.m))); */
                    /* } */

                    // no way this works xd
                    /* nxdphull[k + crk + 1].insert_line(0, -(normi.b - normi.m * normi.m + normx.b - normx.m * normx.m + (normi.m + normx.m) * (normi.m + normx.m))); */
                    // inaczej niż myślałem z tym though
                    /* whatis(best) */
                    /* whatis(Line({normx.m, -(normi.b + normx.b)})) */
                    /* nxdphull[k + crk + 1].insert_line(normx.m, -(normi.b + normx.b)); */
                    // z remowaniem jeszcze -> ezer wgl
                    // omg, inny query do tego przecie lol
                    // pls niech to będzie jedyny powód do wa

                    // ten best mogę zostawić za to (jak i wcześniej) wsm
                    auto best2 = dphull[i][crk].eval_raw(0);
                    /* Line normi2 = {best.m,-best.b}; */
                    Line normi2 = {best2.m,-best2.b};
                    /* whatis(k+crk+1) */
                    /* whatis(normi2) */
                    /* whatis(Line({normx.m, -(normi2.b + normx.b)})); */
                    nxdphull[k + crk + 1].insert_line(normx.m, -(normi2.b + normx.b));
                }
            }
        }
        for(int crk = 0; !nxdphull[crk].empty(); ++crk){
            // weird meme opts
            // rem all that are best only for negative queries
            // and also those that are best only for > nn * 1e6 (nn * max wsm)
            // or even trzym cnt całości, i tego w poddrzewie
            /* if(0){ */

//__        __  _____   _____
//  \ \      / / |_   _| |  ___|
//   \ \ /\ / /    | |   | |_
//    \ V  V /     | |   |  _|
//     \_/\_/      |_|   |_|
//__        __  _____   _____
//  \ \      / / |_   _| |  ___|
//   \ \ /\ / /    | |   | |_
//    \ V  V /     | |   |  _|
//     \_/\_/      |_|   |_|
//__        __  _____   _____
//  \ \      / / |_   _| |  ___|
//   \ \ /\ / /    | |   | |_
//    \ V  V /     | |   |  _|
//     \_/\_/      |_|   |_|
//     TSOOOOOO
//     jak do dak mocno zmniejzsa ilość tego czegoś wtff
//     0.041s na n = 300??????????????????????????????????????????????????

            if(1){
                // wait, przecież ja robię queries od ujemnych XD
                // raczej chcę wywalić te dodatnie lol
                auto l = nxdphull[crk].lower_bound((Line){0,is_qu});
                /* auto it = nxdphull[crk].begin(); */
                /* while(it != l){ */
                /*     ++it; */
                /*     nxdphull[crk].erase(prev(it)); */
                /* } */
                auto it = --nxdphull[crk].end();
                while(it != l){
                    --it;
                    nxdphull[crk].erase(next(it));
                }
            }
            crdphull[crk] = nxdphull[crk];
            /* crdphull[crk] = std::move(nxdphull[crk]); */
            // clear jakiś zły jest?
            nxdphull[crk].clear();
            // uwaga na invalidacje wskaźników w succ
            crdphull[crk].reset_succ();
            /* whatis(crk) */
            /* whatis(crdphull[crk]) */
        }
        /* for(int k = 0; !crdp[k].empty(); ++k){ */
        /*     // Z usuwaniem krawędzi def możemy być sprytniejsi, i wyjąć tylko */
        /*     // jedno stąd for each x i crk */
        /*     // w teorii for each k x + crk może moglibyśmy zoptować */
        /*     FORR(x,crdp[k]){ */
        /*         // nie pętlowanie się tutaj po wszystkich crk byłoby spoko */
        /*         for(int crk = 0; !dp[i][crk].empty(); ++crk){ */
        /*             /1* ll bestremedge = LONG_LONG_MAX; *1/ */
        /*             // CONVEX HULL TRICK HERE? (Jak nie wywalamy adj edgea) */
        /*             // ale ja niekoniecznie chcę zamykać though */
        /*             // -> więc tak na pałę nie mogę tego robić */
        /*             // no bo zostają mi 2 wymiary wtedy */
        /*             FORR(j,dp[i][crk]){ */
        /*                 // bez usuwania direct edgea */
        /*                 /1* rec(it + 1, k + crk, cres + i.first, csum + i.second); *1/ */
        /*                 nxdp[k + crk].push_back({x.first + j.first, x.second + j.second}); */
        /*                 // z usuwaniem direct edgea */
        /*                 /1* nxdp[k + crk + 1].push_back({x.first + j.first + j.second * j.second, x.second}); *1/ */
        /*                 /1* rec(it + 1, k + crk + 1, cres + i.first + i.second * i.second, csum); *1/ */
        /*             } */
        /*             // wykorzystanie dprem */
        /*             // -> time for tests cut in half */
        /*             // now the thing above is def the bottleneck */
        /*             nxdp[k + crk + 1].push_back({x.first + dprem[i][crk], x.second}); */
        /*         } */
        /*         /1* if(bestremedge != LONG_LONG_MAX){ *1/ */
        /*         /1*     nxdp[k + crk + 1].push_back({x.first + j.first + j.second * j.second, x.second}); *1/ */
        /*         /1* } *1/ */
        /*     } */
        /* } */
        // forgot to swap set crdp to nxdp
        /* for(int k = 0; !crdp[k].empty(); ++k){ */
        /*     assert(!nxdp[k].empty()); */
        /* } */
        /* for(int k = 0; !nxdp[k].empty(); ++k){ */
        /*     /1* whatis(k) *1/ */
        /*     /1* whatis(crdp[k].size()) *1/ */
        /*     /1* whatis(nxdp[k].size()) *1/ */
        /*     /1* assert(!crdp[k].empty()); // failed, interesting *1/ */
        /*     // wait, nie taki assert miał być */
        /*     // crdp[k].size() -> nxdp[k].size() */
        /*     // std::move again :? */
        /*     crdp[k] = nxdp[k]; */
        /*     // also, forgot to clear nxdp */
        /*     nxdp[k].clear(); */
        /* } */

        // for debug
        /* vector<pair<ll,ll>> wcrdp[nn]; */
        /* for(int k = 0; !crdp[k].empty(); ++k){ */
        /*     wcrdp[k] = crdp[k]; */
        /* } */

        // this here makes it quite worse eh...
        /* for(int crk = 0; !nxdp[crk].empty(); ++crk){ */
        /*     /1* whatis(crk) *1/ */
        /*     /1* whatis(nn) *1/ */
        /*     /1* bool sth = 0; *1/ */
        /*     FORR(i,nxdp[crk]){ */
        /*         if(i.second){ */
        /*             /1* whatis(crk + 1) *1/ */
        /*             /1* whatis(i.first) *1/ */
        /*             /1* whatis(i.second * i.second) *1/ */
        /*             // this if fixed the segfault somehow */
        /*             if(!nxdp[crk + 1].empty()) */
        /*                 nxdp[crk + 1].push_back({i.first + i.second * i.second, 0}); */
        /*             /1* sth = 1; *1/ */
        /*         } */
        /*     } */
        /*     /1* if(!sth) *1/ */
        /*     /1*     break; *1/ */
        /*     /1* sort(all(crdp[crk])); *1/ */
        /*     /1* vector<pair<ll,ll>> tmp; *1/ */
        /*     /1* FORR(i,crdp[crk]){ *1/ */
        /*     /1*     if(tmp.empty() || tmp.back().e2 > i.e2) *1/ */
        /*     /1*         tmp.push_back(i); *1/ */
        /*     /1* } *1/ */
        /*     /1* whatis(crdp[crk].size() - tmp.size()) *1/ */
        /*     /1* crdp[crk] = std::move(tmp); *1/ */
        /* } */

        // let's do the czystka after each step
        /* for(int crk = 0; !nxdp[crk].empty(); ++crk){ */
        // thx valgrind?
        /* for(int crk = 0; !nxdp[crk].empty(); ++crk){ */
        /*     /1* whatis(nxdp[crk].size()) *1/ */
        /*     sort(all(nxdp[crk])); */
        /*     vector<pair<ll,ll>> tmp; // easier much */
        /*     // mogę tryhardować stałym stackiem */
        /*     // tutaj ładnie to crdp po prostu */
        /*     // ale mogę movenać z tmp po prostu wsm */
        /*     /1* for(int i = 0; i < dp[v][crk].size(); ++i){ *1/ */
        /*     /1*     if(tmp.empty() || tmp.back().e2 > dp[v][crk][i].e2) *1/ */
        /*     /1*         tmp.push_back(dp[v][crk][i]); *1/ */
        /*     /1* } *1/ */
        /*     FORR(i,nxdp[crk]){ */
        /*         if(tmp.empty() || tmp.back().e2 > i.e2) */
        /*             tmp.push_back(i); */
        /*     } */
        /*     /1* whatis(dp[v][crk].size()) *1/ */
        /*     /1* whatis(nxdp[crk].size()) *1/ */
        /*     /1* whatis(tmp.size()) *1/ */
        /*     // ujemne lol */
        /*     // ma sens wsm nvm */
        /*     /1* whatis(dp[v][crk].size() - tmp.size()) *1/ */
        /*     /1* whatis(nxdp[crk].size() - tmp.size()) *1/ */
        /*     // wtf? zawsze zero prawie zawsze */
        /*     // nvm, dochodzi do >100k dla n = 100 */
        /*     // down from 3 miliony jak bez dppre */
        /*     // -> mniej zbędnych insertów jednak i guess */
        /*     /1* whatis( - tmp.size()) *1/ */
        /*     /1* dp[v][crk] = tmp; *1/ */
        /*     /1* crdp[crk] = tmp; *1/ */
        /*     /1* whatis(tmp.size()) *1/ */
        /*     crdp[crk] = std::move(tmp); */
        /*     nxdp[crk].clear(); */
        /* } */

        // thought experiment testowania ile weszło next statów z danej grupy
        // *ternary search potential*?

        /* for(int k = 0; !wcrdp[k].empty(); ++k){ */
        /*     FORR(x,wcrdp[k]){ */
        /*         /1* whatis(x) *1/ */
        /*         for(int crk = 0; !dp[i][crk].empty(); ++crk){ */
        /*             /1* whatis(crk) *1/ */
        /*             // może większy thought jak to posortuję przez csum zamiast cres? */
        /*             sort(all(dp[i][crk]),[](auto f, auto s){return f.second < s.second;}); */
        /*             FORR(j,dp[i][crk]){ */
        /*                 // bez usuwania direct edgea */
        /*                 /1* rec(it + 1, k + crk, cres + i.first, csum + i.second); *1/ */
        /*                 bool sth1 = binary_search(all(crdp[k + crk]),make_pair(x.first + j.first, x.second + j.second)); */
        /*                 // z usuwaniem direct edgea */
        /*                 /1* bool sth2 = binary_search(all(crdp[k + crk + 1]),make_pair(x.first + j.first + j.second * j.second, x.second)); *1/ */
        /*                 // sth2 w sumie łatwe do ogarnięcia czemu tak jest */
        /*                 /1* whatis(sth2) // -> wow, prawie zawsze tylko 1; max 2; ternary def *1/ */
        /*                 /1* whatis(sth1) // ze sth1 za to prawie zawsze WSZYSTKIE; i nie ternary *1/ */
        /*                 // ale może dlatego że się powtarzają? Chyba ta, bo */
        /*                 // inaczej za dużo by tego wychodziło def */
        /*                 /1* rec(it + 1, k + crk + 1, cres + i.first + i.second * i.second, csum); *1/ */
        /*             } */
        /*         } */
        /*     } */
        /* } */
    }

    /* set<pair<ll,ll>> st; */
    /* for(int crk = 0; !crdp[crk].empty(); ++crk){ */
    /*     vector<pair<ll,ll>> tmp; */
    /*     FORR(i,crdp[crk]){ */
    /*         /1* auto it = st.lower_bound(i); *1/ */
    /*         auto it = st.insert(i).e1; */
    /*         // as simple as that? */
    /*         if(it != st.begin() && prev(it)->second <= it->second) */
    /*             st.erase(it); */
    /*         else{ */
    /*             st.erase(it); */
    /*             tmp.push_back(i); */
    /*         } */
    /*         // może (powinno) być lepsze od kolesia z mniejszego k obv */
    /*         // -> jeszcze check czy jest w sumie? */
    /*         // -> nie wywalanie tylko gorszych, lecz też tych *nie lepszych* */
    /*         // tylko wtedy muszę później dopieru insertować do seta też */
    /*         // ale jednak tutaj zawsze będzie ten partial lepszy / gorszy */
    /*         // czyli tak jak jest -> git */
    /*     } */
    /*     whatis(crdp[crk].size() - tmp.size()) */
    /*     FORR(i,tmp) */
    /*         st.insert(i); */
    /*     // -> XD, all 0 na samplach hmmm */
    /*     // rzeczywiście *bardzo* mało to daje... */
    /*     crdp[crk] = std::move(tmp); */
    /* } */

    /* for(int crk = 0; !crdp[crk].empty(); ++crk){ */
    /*     /1* whatis(crk) *1/ */
    /*     /1* whatis(nn) *1/ */
    /*     /1* bool sth = 0; *1/ */
    /*     FORR(i,crdp[crk]){ */
    /*         if(i.second){ */
    /*             /1* whatis(crk + 1) *1/ */
    /*             /1* whatis(i.first) *1/ */
    /*             /1* whatis(i.second * i.second) *1/ */
    /*             // this if fixed the segfault somehow */
    /*             if(!crdp[crk + 1].empty()) */
    /*                 crdp[crk + 1].push_back({i.first + i.second * i.second, 0}); */
    /*             /1* sth = 1; *1/ */
    /*         } */
    /*     } */
    /*     /1* if(!sth) *1/ */
    /*     /1*     break; *1/ */
    /*     sort(all(crdp[crk])); */
    /*     vector<pair<ll,ll>> tmp; */
    /*     FORR(i,crdp[crk]){ */
    /*         if(tmp.empty() || tmp.back().e2 > i.e2) */
    /*             tmp.push_back(i); */
    /*     } */
    /*     whatis(crdp[crk].size() - tmp.size()) */
    /*     crdp[crk] = std::move(tmp); */
    /* } */

    // dprem
    /* for(int crk = 0; !crdp[crk].empty(); ++crk){ */
    /*     FORR(i,crdp[crk]){ */
    /*         dprem[v][crk] = min(dprem[v][crk], i.first + i.second * i.second); */
    /*     } */
    /* } */

    /* ll s = 0; */
    /* for(int crk = 0; !crdp[crk].empty(); ++crk){ // nn = n + 2, bo inaczej mogłobybyć rip z checkiem !crdp[n].empty() */
    /*     // std::move kappa */
    /*     /1* dp[v][crk] = crdp[crk]; *1/ */
    /*     dp[v][crk] = std::move(crdp[crk]); */

    /*     // let's change this to after each step */
    /*     /1* sort(all(dp[v][crk])); *1/ */
    /*     /1* vector<pair<ll,ll>> tmp; // easier much *1/ */
    /*     /1* // mogę tryhardować stałym stackiem *1/ */
    /*     /1* for(int i = 0; i < dp[v][crk].size(); ++i){ *1/ */
    /*     /1*     if(tmp.empty() || tmp.back().e2 > dp[v][crk][i].e2) *1/ */
    /*     /1*         tmp.push_back(dp[v][crk][i]); *1/ */
    /*     /1* } *1/ */

    /*     // zróbmy teraz coś jeszcze, co może być istotniejsze */
    /*     // -> między RÓŻNYMI k wywalajmy def nieoptymalne statey */
    /*     // tmp set without prev removal? */
    /*     // i guess that's the simplest thing to do */
    /*     // ewentualnie merge vectorów dobrych po prostu */
    /*     // ale let's go with set i guess */

    /*     /1* whatis(dp[v][crk].size()) *1/ */
    /*     s += dp[v][crk].size(); */
    /*     /1* whatis(tmp.size()) *1/ */
    /*     /1* whatis(dp[v][crk].size() - tmp.size()) *1/ */
    /*     /1* dp[v][crk] = tmp; *1/ */
    /* } */
    /* whatis(s) */
    ll s = 0;
    for(int crk = 0; !crdphull[crk].empty(); ++crk){ // nn = n + 2, bo inaczej mogłobybyć rip z checkiem !crdp[n].empty()
        /* dphull[v][crk] = std::move(crdphull[crk]); */
        dphull[v][crk] = crdphull[crk];
        dphull[v][crk].reset_succ(); // -> nicee
        s += dphull[v][crk].size();
    }
    /* whatis(s) */
    szsum[v] = s;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int t;
    sc(t);
    while(t--){
        int n;
        sc(n);
        nn = n + 2;
        FOR(i,0,n)
            adj[i].clear();
        FOR(i,0,n){
            sc(val[i]);
        }
        FOR(i,0,n){
            /* for(int crk = 0; !dp[i][crk].empty(); ++crk){ */
            /*     dp[i][crk].clear(); */
            /* } */
            // safety is cool
            FOR(k,0,n){
                dp[i][k].clear();
                dphull[i][k].clear(); // TODO
                // może nie MAX, bo overflow much
                /* dprem[i][k] = LONG_LONG_MAX; */
                dprem[i][k] = LONG_LONG_MAX / 32;
            }
        }
        int f,s;
        FOR(i,1,n){
            sc(f,s);
            --f,--s;
            adj[f].pb(s);
            adj[s].pb(f);
        }
        d1(0,-1);
        /* for(int k = 0; k < n; ++k){ */
        /*     ll crres = LONG_LONG_MAX; */
        /*     FORR(i,dp[0][k]){ */
        /*         crres = min(crres, i.e1 + i.e2 * i.e2); */
        /*     } */
        /*     cout << crres << ' '; */
        /* } */
        for(int k = 0; k < n; ++k){
            ll crres = -dphull[0][k].eval(0);
            /* FORR(i,dp[0][k]){ */
            /*     crres = min(crres, i.e1 + i.e2 * i.e2); */
            /* } */
            cout << crres << ' ';
        }
        cout << '\n';
    }
    // -> Nice, again za *basically* pierwszym runem przeszło sampla
}