#define _USE_MATH_DEFINES #include <bits/stdc++.h> #ifdef LOC #include "debuglib.h" #else #define deb(...) #define DBP(...) #endif using namespace std; using ll = long long; using Vi = vector<int>; using Pii = pair<int, int>; #define pb push_back #define mp make_pair #define x first #define y second #define rep(i, b, e) for (int i = (b); i < (e); i++) #define each(a, x) for (auto& a : (x)) #define all(x) (x).begin(), (x).end() #define sz(x) int((x).size()) using Pll = pair<ll, ll>; using dbl = long double; Pll operator+(Pll a, Pll b) { return {a.x+b.x, a.y+b.y}; } Pll operator-(Pll a, Pll b) { return {a.x-b.x, a.y-b.y}; } int n; vector<ll> vals; vector<Vi> G; bool crossSign(Pll a, Pll b) { return dbl(a.x)*dbl(b.y) > dbl(a.y)*dbl(b.x); } void reduce(vector<Pll>& out, vector<Pll>& in) { sort(all(in)); out.clear(); each(p, in) { while (sz(out) >= 2) { Pll a = out.back() - out[sz(out)-2]; Pll b = p - out.back(); if (crossSign(a, b)) break; out.pop_back(); } out.pb(p); } while (sz(out) >= 2 && out[sz(out)-2].y < out.back().y) { out.pop_back(); } } void reduce(vector<vector<Pll>>& out, vector<vector<Pll>>& in) { out.resize(sz(in)); rep(i, 0, sz(in)) { reduce(out[i], in[i]); } } vector<vector<Pll>> dfs(int v, int par) { vector<vector<Pll>> agg(1); agg[0].pb({ vals[v]*2, vals[v]*vals[v] }); each(e, G[v]) if (e != par) { auto sub = dfs(e, v); vector<vector<Pll>> tmp(sz(agg) + sz(sub) - 1); rep(i, 0, sz(agg)) rep(j, 0, sz(sub)) { each(p, agg[i]) each(q, sub[j]) { tmp[i+j].pb({ p.x + q.x, p.y + q.y + p.x*q.x/2 }); } } reduce(agg, tmp); } auto tmp = agg; tmp.resize(sz(agg)+1); rep(i, 0, sz(agg)) { each(p, agg[i]) { tmp[i+1].pb({ 0, p.y }); } } reduce(agg, tmp); return agg; } void run() { cin >> n; vals.resize(n); G.assign(n, {}); each(v, vals) { cin >> v; } rep(i, 1, n) { int u, v; cin >> u >> v; G[u-1].pb(v-1); G[v-1].pb(u-1); } auto dp = dfs(0, -1); rep(k, 1, n+1) { assert(dp[k][0].x == 0); cout << dp[k][0].y << ' '; } cout << '\n'; } int main() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); int t; cin >> t; while (t--) run(); 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 | #define _USE_MATH_DEFINES #include <bits/stdc++.h> #ifdef LOC #include "debuglib.h" #else #define deb(...) #define DBP(...) #endif using namespace std; using ll = long long; using Vi = vector<int>; using Pii = pair<int, int>; #define pb push_back #define mp make_pair #define x first #define y second #define rep(i, b, e) for (int i = (b); i < (e); i++) #define each(a, x) for (auto& a : (x)) #define all(x) (x).begin(), (x).end() #define sz(x) int((x).size()) using Pll = pair<ll, ll>; using dbl = long double; Pll operator+(Pll a, Pll b) { return {a.x+b.x, a.y+b.y}; } Pll operator-(Pll a, Pll b) { return {a.x-b.x, a.y-b.y}; } int n; vector<ll> vals; vector<Vi> G; bool crossSign(Pll a, Pll b) { return dbl(a.x)*dbl(b.y) > dbl(a.y)*dbl(b.x); } void reduce(vector<Pll>& out, vector<Pll>& in) { sort(all(in)); out.clear(); each(p, in) { while (sz(out) >= 2) { Pll a = out.back() - out[sz(out)-2]; Pll b = p - out.back(); if (crossSign(a, b)) break; out.pop_back(); } out.pb(p); } while (sz(out) >= 2 && out[sz(out)-2].y < out.back().y) { out.pop_back(); } } void reduce(vector<vector<Pll>>& out, vector<vector<Pll>>& in) { out.resize(sz(in)); rep(i, 0, sz(in)) { reduce(out[i], in[i]); } } vector<vector<Pll>> dfs(int v, int par) { vector<vector<Pll>> agg(1); agg[0].pb({ vals[v]*2, vals[v]*vals[v] }); each(e, G[v]) if (e != par) { auto sub = dfs(e, v); vector<vector<Pll>> tmp(sz(agg) + sz(sub) - 1); rep(i, 0, sz(agg)) rep(j, 0, sz(sub)) { each(p, agg[i]) each(q, sub[j]) { tmp[i+j].pb({ p.x + q.x, p.y + q.y + p.x*q.x/2 }); } } reduce(agg, tmp); } auto tmp = agg; tmp.resize(sz(agg)+1); rep(i, 0, sz(agg)) { each(p, agg[i]) { tmp[i+1].pb({ 0, p.y }); } } reduce(agg, tmp); return agg; } void run() { cin >> n; vals.resize(n); G.assign(n, {}); each(v, vals) { cin >> v; } rep(i, 1, n) { int u, v; cin >> u >> v; G[u-1].pb(v-1); G[v-1].pb(u-1); } auto dp = dfs(0, -1); rep(k, 1, n+1) { assert(dp[k][0].x == 0); cout << dp[k][0].y << ' '; } cout << '\n'; } int main() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); int t; cin >> t; while (t--) run(); return 0; } |