#include <cstdio> #include <vector> using namespace std; vector<vector<int> > v; vector<int> kol, oj, a; vector<long long> ss; vector<long long> wyn; void go(int xx, int c, long long s2) { // printf("wej %d %d %lld\n",xx,c,s2); if (xx == kol.size()) { wyn[c] = std::min(wyn[c], s2); return; } int x = kol[xx]; if (oj[x] > 0) { ss[oj[x]] += ss[x]; go(xx+1, c, s2); ss[oj[x]] -= ss[x]; } long long a = ss[x]; go(xx+1, c+1, s2 + a*a); } int dfs(int x, int o = -1) { int ret = 0; oj[x] = o; for (int i = 0; i < v[x].size(); i++) { int y = v[x][i]; if (y != o) { ret = std::max(ret, 1 + dfs(y, x)); } } kol.push_back(x); return ret; } void tcase() { int n; scanf("%d",&n); wyn = vector<long long>(n+1, ((long long)1e18)); a = vector<int>(n+1); v = vector<vector<int> >(n+1); oj = vector<int>(n+1); kol.clear(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); ss = vector<long long>(a.begin(), a.end()); for (int i = 0; i < n-1; i++) { int x,y; scanf("%d %d",&x,&y); v[x].push_back(y); v[y].push_back(x); } dfs(1); go(0,0,0); for (int i = 1; i <= n; i++) printf("%lld ", wyn[i]); printf("\n"); { /* vector<int> dd(n+1); for (int i = 1; i <= n; i++) dd[v[i].size()]++; while(dd.back() == 0) dd.pop_back(); // stopnie for (int i = 1; i < dd.size(); i++) printf("%d ", dd[i]); printf("\n"); // */ } } int main() { int tt; scanf("%d",&tt); while(tt--) { tcase(); } 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 | #include <cstdio> #include <vector> using namespace std; vector<vector<int> > v; vector<int> kol, oj, a; vector<long long> ss; vector<long long> wyn; void go(int xx, int c, long long s2) { // printf("wej %d %d %lld\n",xx,c,s2); if (xx == kol.size()) { wyn[c] = std::min(wyn[c], s2); return; } int x = kol[xx]; if (oj[x] > 0) { ss[oj[x]] += ss[x]; go(xx+1, c, s2); ss[oj[x]] -= ss[x]; } long long a = ss[x]; go(xx+1, c+1, s2 + a*a); } int dfs(int x, int o = -1) { int ret = 0; oj[x] = o; for (int i = 0; i < v[x].size(); i++) { int y = v[x][i]; if (y != o) { ret = std::max(ret, 1 + dfs(y, x)); } } kol.push_back(x); return ret; } void tcase() { int n; scanf("%d",&n); wyn = vector<long long>(n+1, ((long long)1e18)); a = vector<int>(n+1); v = vector<vector<int> >(n+1); oj = vector<int>(n+1); kol.clear(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); ss = vector<long long>(a.begin(), a.end()); for (int i = 0; i < n-1; i++) { int x,y; scanf("%d %d",&x,&y); v[x].push_back(y); v[y].push_back(x); } dfs(1); go(0,0,0); for (int i = 1; i <= n; i++) printf("%lld ", wyn[i]); printf("\n"); { /* vector<int> dd(n+1); for (int i = 1; i <= n; i++) dd[v[i].size()]++; while(dd.back() == 0) dd.pop_back(); // stopnie for (int i = 1; i < dd.size(); i++) printf("%d ", dd[i]); printf("\n"); // */ } } int main() { int tt; scanf("%d",&tt); while(tt--) { tcase(); } return 0; } |