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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <bits/stdc++.h>
typedef long long LL;
using std::vector;

struct Vertex {
  LL weight = 0;
  vector<Vertex*> edges;
};

struct SubtreeSolution {
  LL sum_squares = 0;
  LL top_component = 0;
};

// [num cuts] => list of solutions sorted by increasing sum_squares, decreasing top_component
using SubtreeSolutions = vector<vector<SubtreeSolution>>;

SubtreeSolutions solve_one_vertex(Vertex *v) {
  return {
    // 0 cuts
    {
      // only one way
      SubtreeSolution { v->weight * v->weight, v->weight }
    }
  };
}

SubtreeSolution merge_solution(const SubtreeSolution &a, const SubtreeSolution &b) {
  return SubtreeSolution {
    a.sum_squares + b.sum_squares + 2u * a.top_component * b.top_component,
    a.top_component + b.top_component
  };
}

void reduce_solutions(vector<SubtreeSolution> &v) {
  std::sort(v.begin(), v.end(),
    [](const SubtreeSolution &a, const SubtreeSolution &b) {
      if (a.sum_squares != b.sum_squares) return a.sum_squares < b.sum_squares;
      return a.top_component < b.top_component;
    }
  );

  auto end = v.begin();
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (end == v.begin() || (end-1)->top_component > it->top_component) {
      *end = *it;
      ++end;
    }
  }

  v.erase(end, v.end());
}

SubtreeSolutions merge_solutions(const SubtreeSolutions &a, const SubtreeSolutions &b) {
  SubtreeSolutions solutions(a.size() + b.size()-1u);

  for (size_t cuts_a = 0; cuts_a < a.size(); ++cuts_a) {
    for (size_t cuts_b = 0; cuts_b < b.size(); ++cuts_b) {
      for (const SubtreeSolution &sol_a : a[cuts_a]) {
        for (const SubtreeSolution &sol_b: b[cuts_b]) {
          solutions[cuts_a + cuts_b].push_back(merge_solution(sol_a, sol_b));
        }
      }
    }
  }

  for (auto &v : solutions) {
    reduce_solutions(v);
  }

  return solutions;
}

void add_top_edge(SubtreeSolutions &solutions) {
  const size_t n = solutions.size();
  solutions.emplace_back();
  for (size_t cuts=n;cuts>=1u;--cuts) {
    LL sum_squares = solutions[cuts-1].front().sum_squares;
    auto &v = solutions[cuts];
    while (!v.empty() && v.back().sum_squares >= sum_squares) {
      v.pop_back();
    }
    v.push_back(SubtreeSolution { sum_squares, 0 });
  }
}

SubtreeSolutions solve_subtree(Vertex *v, Vertex *parent) {
  SubtreeSolutions solutions = solve_one_vertex(v);

  for (Vertex *child : v->edges) {
    if (child == parent) continue;

    SubtreeSolutions child_solutions = solve_subtree(child, v);
    add_top_edge(child_solutions);
    solutions = merge_solutions(solutions, child_solutions);
  }
  return solutions;
}

class Tree {
public:
  Tree();
  vector<LL> solve();
private:
  vector<Vertex> vertices;
};

Tree::Tree() {
  int n;
  std::cin >> n;
  vertices.resize(n);
  for (int i=0;i<n;++i) {
    std::cin >> vertices[i].weight;
  }
  for (int i=0;i<n-1;++i) {
    int a,b;
    std::cin >> a >> b;
    --a; --b;
    vertices[a].edges.push_back(&vertices[b]);
    vertices[b].edges.push_back(&vertices[a]);
  }
}

vector<LL> Tree::solve() {
  const auto root_solution = solve_subtree(&vertices[0], nullptr);
  assert(root_solution.size() == vertices.size());
  vector<LL> res;
  res.reserve(vertices.size());
  for (const auto &solutions : root_solution) {
    assert(!solutions.empty());
    res.push_back(solutions.front().sum_squares);
  }
  return res;
}

void print_result(const vector<LL> &res) {
  for (LL x : res) {
    std::cout << x << " ";
  }
  std::cout << "\n";
}

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int ntc;
  std::cin >> ntc;
  for (int tc=0; tc<ntc; ++tc) {
    Tree tree;
    const auto res = tree.solve();
    print_result(res);
  }
}