Niyaz has a tree with $n$ vertices numerated from $1$ to $n$. A tree is a connected graph without cycles.
Each edge in this tree has strictly positive integer weight. A degree of a vertex is the number of edges adjacent to this vertex.
Niyaz does not like when vertices in the tree have too large degrees. For each $x$ from $0$ to $(n-1)$, he wants to find the smallest total weight of a set of edges to be deleted so that degrees of all vertices become at most $x$.
Input
The first line contains a single integer $n$ ($2 \le n \le 250\,000$) — the number of vertices in Niyaz’s tree.
Each of the next $(n – 1)$ lines contains three integers $a$, $b$, $c$ ($1 \le a, b \le n$, $1 \leq c \leq 10^6$) — the indices of the vertices connected by this edge and its weight, respectively. It is guaranteed that the given edges form a tree.
Output
Print $n$ integers: for each $x = 0, 1, \ldots, (n-1)$ print the smallest total weight of such a set of edges that after one deletes the edges from the set, the degrees of all vertices become less than or equal to $x$.
Examples
input
5 1 2 1 1 3 2 1 4 3 1 5 4
output
10 6 3 1 0
input
5 1 2 1 2 3 2 3 4 5 4 5 14
output
22 6 0 0 0
Note
In the first example, the vertex $1$ is connected with all other vertices. So for each $x$ you should delete the $(4-x)$ lightest edges outgoing from vertex $1$, so the answers are $1+2+3+4$, $1+2+3$, $1+2$, $1$ and $0$.
In the second example, for $x=0$ you need to delete all the edges, for $x=1$ you can delete two edges with weights $1$ and $5$, and for $x \geq 2$ it is not necessary to delete edges, so the answers are $1+2+5+14$, $1+5$, $0$, $0$ and $0$.
Solution:
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<vector<pair<int, int>>> graph(n); long long total = 0; for (int i = 0; i < n - 1; i++) { int x, y, z; cin >> x >> y >> z; x--; y--; graph[x].emplace_back(y, z); graph[y].emplace_back(x, z); total += z; } vector<vector<int>> at_deg(n); vector<int> deg(n); for (int i = 0; i < n; i++) { deg[i] = (int) graph[i].size(); at_deg[deg[i]].push_back(i); } vector<vector<pair<int, int>>> g(n); vector<int> alive(n, 0); vector<multiset<int>> extra_small(n); vector<multiset<int>> extra_big(n); vector<long long> sum_extra_big(n, 0); vector<long long> res(n, 0); set<int> lovers; long long saved = total; vector<int> was(n, -1); for (int dd = n - 1; dd >= 1; dd--) { auto BalanceOver = [&](int v) { while ((int) extra_big[v].size() > dd) { auto it = extra_big[v].begin(); sum_extra_big[v] -= *it; extra_small[v].insert(*it); extra_big[v].erase(it); } }; auto BalanceUnder = [&](int v) { while ((int) extra_big[v].size() < dd && !extra_small[v].empty()) { auto it = prev(extra_small[v].end()); sum_extra_big[v] += *it; extra_big[v].insert(*it); extra_small[v].erase(it); } }; auto Add = [&](int x, int y) { extra_big[x].insert(y); sum_extra_big[x] += y; BalanceOver(x); }; auto Remove = [&](int x, int y) { auto it = extra_small[x].find(y); if (it != extra_small[x].end()) { extra_small[x].erase(it); } else { it = extra_big[x].find(y); assert(it != extra_big[x].end()); extra_big[x].erase(it); sum_extra_big[x] -= y; BalanceUnder(x); } }; for (int v : lovers) { BalanceOver(v); } function<pair<long long, long long>(int, int)> dfs = [&](int v, int pr) -> pair<long long, long long> { was[v] = dd; vector<long long> saveable; long long overall = 0; long long total_saveable = 0; int up_cost = 0; for (auto& p : g[v]) { int to = p.first; int cost = p.second; if (to == pr) { up_cost = cost; continue; } auto z = dfs(to, v); overall += z.first; if (z.second > z.first) { saveable.push_back(z.second - z.first); total_saveable += z.second - z.first; } } sort(saveable.begin(), saveable.end()); int cnt = (int) saveable.size() + (int) extra_big[v].size(); long long val = overall + total_saveable + sum_extra_big[v]; int i = 0; auto it = extra_big[v].begin(); long long tmp0 = -1; long long tmp1 = -1; for (int rot = 0; rot < 2; rot++) { while (cnt > dd - rot) { if (it == extra_big[v].end() || (i < (int) saveable.size() && saveable[i] < *it)) { val -= saveable[i]; ++i; } else { val -= *it; ++it; } cnt--; } if (rot == 0) { tmp0 = val; } else { tmp1 = val; } } return make_pair(tmp0, tmp1 + up_cost); }; long long dp = 0; for (int v : lovers) { if (was[v] == dd) { continue; } auto p = dfs(v, -1); dp += p.first; } res[dd] = total - (saved + dp); for (int v : at_deg[dd]) { for (auto& p : graph[v]) { int u = p.first; int cost = p.second; if (alive[u]) { g[v].emplace_back(u, cost); g[u].emplace_back(v, cost); Remove(u, cost); } else { Add(v, cost); saved -= cost; } } alive[v] = 1; lovers.insert(v); } } res[0] = total; for (int i = 0; i < n; i++) { if (i > 0) { cout << " "; } cout << res[i]; } cout << '\n'; return 0; }