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;
}
