#include <bits/stdc++.h> using namespace std; typedef long long int LL; #define st first #define nd second #define PLL pair <LL, LL> const int N = 307; int n; int sz[N]; int vals[N]; vector <int> G[N]; vector <PLL> tmp[N]; vector <PLL> dp[N][N]; void read() { scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &vals[i]); for(int i = 1; i < n; ++i) { int u, v; scanf("%d %d", &u, &v); G[u].push_back(v); G[v].push_back(u); } } vector <PLL> parse(vector <PLL> &in) { sort(in.begin(), in.end()); vector <PLL> result; for(auto [s, v]: in) { if(result.size() == 0) result.push_back({s, v}); else { auto [s2, v2] = result.back(); if(s2 * s2 + v2 > s * s + v) result.push_back({s, v}); } } return result; } void push(vector <PLL> &to_push, const vector <PLL> &Left, const vector <PLL> &Right) { for(const auto &[ls, lv] : Left) for(const auto &[rs, rv]: Right) to_push.push_back({ls + rs, lv + rv}); } void merge(int &fa, int &fb) { for(int i = 0; i < sz[fa] + sz[fb]; ++i) tmp[i].clear(); for(int ca = 0; ca < sz[fa]; ++ca) { for(int cb = 0; cb < sz[fb]; ++cb) { push(tmp[ca + cb], dp[fa][ca], dp[fb][cb]); auto [ts, tv] = dp[fb][cb].back(); for(auto [s, v]: dp[fa][ca]) tmp[ca + cb + 1].push_back({s, v + tv + ts * ts}); } } sz[fa] += sz[fb]; for(int i = 0; i < sz[fa]; ++i) { dp[fa][i] = parse(tmp[i]); } } void go(int u, int p) { sz[u] = 1; dp[u][0] = {{vals[u], 0}}; for(auto v: G[u]) if(v != p) { go(v, u); merge(u, v); } } void solve() { /* TODO?: Pick centroid as root */ go(1, 0); } void write() { for(int i = 0; i < n; ++i) { auto [s, v] = dp[1][i].back(); printf("%lld%c", s * s + v, " \n"[i + 1 == n]); } } void clear() { for(int i = 1; i <= n; ++i) { for(int j = 0; j < sz[i]; ++j) dp[i][j].clear(); sz[i] = 0; G[i].clear(); } } int main() { int tests; scanf("%d", &tests); while(tests--) { read(); solve(); write(); clear(); } return 0; }
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 113 114 115 116 117 118 119 120 121 122 | #include <bits/stdc++.h> using namespace std; typedef long long int LL; #define st first #define nd second #define PLL pair <LL, LL> const int N = 307; int n; int sz[N]; int vals[N]; vector <int> G[N]; vector <PLL> tmp[N]; vector <PLL> dp[N][N]; void read() { scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &vals[i]); for(int i = 1; i < n; ++i) { int u, v; scanf("%d %d", &u, &v); G[u].push_back(v); G[v].push_back(u); } } vector <PLL> parse(vector <PLL> &in) { sort(in.begin(), in.end()); vector <PLL> result; for(auto [s, v]: in) { if(result.size() == 0) result.push_back({s, v}); else { auto [s2, v2] = result.back(); if(s2 * s2 + v2 > s * s + v) result.push_back({s, v}); } } return result; } void push(vector <PLL> &to_push, const vector <PLL> &Left, const vector <PLL> &Right) { for(const auto &[ls, lv] : Left) for(const auto &[rs, rv]: Right) to_push.push_back({ls + rs, lv + rv}); } void merge(int &fa, int &fb) { for(int i = 0; i < sz[fa] + sz[fb]; ++i) tmp[i].clear(); for(int ca = 0; ca < sz[fa]; ++ca) { for(int cb = 0; cb < sz[fb]; ++cb) { push(tmp[ca + cb], dp[fa][ca], dp[fb][cb]); auto [ts, tv] = dp[fb][cb].back(); for(auto [s, v]: dp[fa][ca]) tmp[ca + cb + 1].push_back({s, v + tv + ts * ts}); } } sz[fa] += sz[fb]; for(int i = 0; i < sz[fa]; ++i) { dp[fa][i] = parse(tmp[i]); } } void go(int u, int p) { sz[u] = 1; dp[u][0] = {{vals[u], 0}}; for(auto v: G[u]) if(v != p) { go(v, u); merge(u, v); } } void solve() { /* TODO?: Pick centroid as root */ go(1, 0); } void write() { for(int i = 0; i < n; ++i) { auto [s, v] = dp[1][i].back(); printf("%lld%c", s * s + v, " \n"[i + 1 == n]); } } void clear() { for(int i = 1; i <= n; ++i) { for(int j = 0; j < sz[i]; ++j) dp[i][j].clear(); sz[i] = 0; G[i].clear(); } } int main() { int tests; scanf("%d", &tests); while(tests--) { read(); solve(); write(); clear(); } return 0; } |