#include "roads.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ostree;
const int MAXN = 1e5+5;
vector<pii> edges[MAXN];
vector<pii> active[MAXN];
vector<int> at_deg[MAXN];
vector<int> cur_active;
ostree adj_inactive[MAXN];
bool activated[MAXN];
ll preset[MAXN];
bool vis[MAXN];
ll dp[MAXN][2];
int n;
void activate(int v, int k) {
activated[v] = 1;
cur_active.push_back(v);
for (pii p: edges[v]) { // order returns num strictly less than
int nxt = p.first;
int ord = adj_inactive[nxt].order_of_key(pii(p.second, v));
adj_inactive[nxt].erase(pii(p.second, v));
if (activated[nxt]) {
if (ord < edges[nxt].size()-k) {
preset[nxt] -= p.second;
if (adj_inactive[nxt].size() >= edges[nxt].size()-k) {
preset[nxt] += adj_inactive[nxt].find_by_order(edges[nxt].size()-k-1)->first;
}
}
active[v].push_back(p);
active[nxt].push_back(pii(v, p.second));
}
}
}
ll trade(int cur, int &req, int &pre_pos, ll cur_cost, bool force = 0) {
if (req) {
req--;
return cur_cost;
}
if (pre_pos < 0) {
if (force) {
req = max(0, req-1);
return cur_cost;
}
return 0;
}
// assert(pre_pos >= 0);
int adj_cost = adj_inactive[cur].find_by_order(pre_pos)->first;
if (cur_cost < adj_cost || force) {
--pre_pos;
return cur_cost-adj_cost;
}
return 0;
}
void dfs(int cur, int k, pii par) {
if (vis[cur]) return;
vis[cur] = 1;
for (int j = 0; j < 2; j++) {
if (par.second == -1 && j) continue;
vector<ll> costs;
ll ans = preset[cur];
for (pii p: active[cur]) {
if (p.first == par.first) continue;
dfs(p.first, k, pii(cur, p.second));
ans += dp[p.first][0];
costs.push_back(dp[p.first][1]-dp[p.first][0]);
}
int req = max(0, (int)edges[cur].size()-k-(int)adj_inactive[cur].size());
// cerr << cur << ' ' << req << '\n';
int pre_pos = min((int)adj_inactive[cur].size()-1, (int)edges[cur].size()-k-1);
if (j) {
ans += trade(cur, req, pre_pos, par.second, 1);
}
else if (par.second != -1) costs.push_back(par.second);
sort(costs.begin(), costs.end());
for (ll cost: costs) ans += trade(cur, req, pre_pos, cost);
assert(req == 0);
dp[cur][j] = ans;
}
}
void expand(int cur, int k) {
if (adj_inactive[cur].size() >= edges[cur].size()-k)
preset[cur] += adj_inactive[cur].find_by_order(edges[cur].size()-k-1)->first;
}
vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
n = N;
for (int i = 0; i < n-1; i++) {
edges[U[i]].push_back(pii(V[i], W[i]));
edges[V[i]].push_back(pii(U[i], W[i]));
adj_inactive[U[i]].insert(pii(W[i], V[i]));
adj_inactive[V[i]].insert(pii(W[i], U[i]));
}
for (int i = 0; i < n; i++) at_deg[edges[i].size()].push_back(i);
vector<ll> ans(n, 0);
for (int k = n-1; k >= 0; k--) {
// cerr << "start of " << k << "\n";
for (int v: at_deg[k+1]) activate(v, k+1);
for (int v: cur_active) expand(v, k);
for (int v: cur_active) {
if (vis[v]) continue;
dfs(v, k, pii(-1, -1));
ans[k] += dp[v][0];
}
for (int v: cur_active) vis[v] = 0;
}
return ans;
}
