#include <bits/stdc++.h> using namespace std; #define mk make_pair #define fst first #define sz(x) x.size() #define snd second #define pb push_back #define VAR(v) #v << " = " << v << " " #define debug if(0) #define M_PI 3.14159265358979323846 typedef complex<long double> C; typedef long long ll; typedef pair<int, int> ii; typedef vector<ll> Matrix; const int maxn = (int)300 + 9; const int INF = (int)1e9 + 7; int mod = (int)1e9 + 7; int n; vector<ii> G[maxn]; ll w[maxn]; ll ans[maxn]; bool vis[maxn]; ll DFS(int v, int sub){ vis[v] = true; ll ret = w[v]; for(ii pu : G[v]) if((1<<pu.snd) & sub && !vis[pu.fst]) ret += DFS(pu.fst, sub); return ret; } void solve(){ cin>>n; for(int i = 1; i <= n; i++) cin>>w[i]; for(int i = 0; i <= n; i++) { ans[i] = (ll(INF))*(ll(INF)); G[i].clear(); } for(int i = 0; i < n - 1; i++){ int u, v; cin>>u>>v; G[u].pb(mk(v, i)); G[v].pb(mk(u, i)); } for(int sub = 0; sub < (1<<n); sub++) { ll res = 0; for(int i = 0; i <= n; i++) vis[i] = false; for(int v = 1; v <= n; v++) if(!vis[v]) { ll val = DFS(v, sub); res += val*val; } int k = 1; for(int i = 0; i < n - 1; i++) if((1<<i) & sub) k++; ans[k] = min(ans[k], res); } for(int i = n; i; i--) cout<<ans[i]<<" "; cout<<"\n"; } int main(int argc, char* argv[]) { ios::sync_with_stdio(false); debug; else cin.tie(NULL), cout.tie(NULL); int test_cases; cin>>test_cases; while(test_cases--) solve(); 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 | #include <bits/stdc++.h> using namespace std; #define mk make_pair #define fst first #define sz(x) x.size() #define snd second #define pb push_back #define VAR(v) #v << " = " << v << " " #define debug if(0) #define M_PI 3.14159265358979323846 typedef complex<long double> C; typedef long long ll; typedef pair<int, int> ii; typedef vector<ll> Matrix; const int maxn = (int)300 + 9; const int INF = (int)1e9 + 7; int mod = (int)1e9 + 7; int n; vector<ii> G[maxn]; ll w[maxn]; ll ans[maxn]; bool vis[maxn]; ll DFS(int v, int sub){ vis[v] = true; ll ret = w[v]; for(ii pu : G[v]) if((1<<pu.snd) & sub && !vis[pu.fst]) ret += DFS(pu.fst, sub); return ret; } void solve(){ cin>>n; for(int i = 1; i <= n; i++) cin>>w[i]; for(int i = 0; i <= n; i++) { ans[i] = (ll(INF))*(ll(INF)); G[i].clear(); } for(int i = 0; i < n - 1; i++){ int u, v; cin>>u>>v; G[u].pb(mk(v, i)); G[v].pb(mk(u, i)); } for(int sub = 0; sub < (1<<n); sub++) { ll res = 0; for(int i = 0; i <= n; i++) vis[i] = false; for(int v = 1; v <= n; v++) if(!vis[v]) { ll val = DFS(v, sub); res += val*val; } int k = 1; for(int i = 0; i < n - 1; i++) if((1<<i) & sub) k++; ans[k] = min(ans[k], res); } for(int i = n; i; i--) cout<<ans[i]<<" "; cout<<"\n"; } int main(int argc, char* argv[]) { ios::sync_with_stdio(false); debug; else cin.tie(NULL), cout.tie(NULL); int test_cases; cin>>test_cases; while(test_cases--) solve(); return 0; } |