#include "roads.h"
//OP
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pi pair<int, int >
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define mset multiset
#define F first
#define S second
#define meta int M = (L + R) / 2, x = 2 * id + 1, y = x + 1
using namespace std;
bool vis[100005];
lnl dp[100005][2];
vector<int> deg[100005];
vector<pi > adj[100005];
vector<pi > cur[100005];
struct Tree {
int n;
vector<lnl> sum;
vector<lnl> val;
vector<int> ct;
void update(int id, int L, int R, int k, int v) {
if (L == R) {sum[id] += v * val[L]; ct[id] += v; return;} meta;
(k <= M ? update(x, L, M, k, v) : update(y, M + 1, R, k, v));
sum[id] = sum[x] + sum[y]; ct[id] = ct[x] + ct[y];
} void update(int w, int v) {update(0, 0, n-1, lb(all(val), w) - val.begin(), v);}
int find(int id, int L, int R, int k) {
if (ct[id] < k) return 2e9;
if (L == R) {return val[L];} meta;
return (ct[x] >= k ? find(x, L, M, k) : find(y, M + 1, R, k - ct[x]));
} int find(int x) {return find(0, 0, n-1, x);}
lnl findsum(int id, int L, int R, int k) {
if (ct[id] <= k) return sum[id]; if (k == 0) return 0;
if (L == R) {return k * val[L];}
meta; int S = findsum(x, L, M, k);
return (ct[x] >= k ? S : S + findsum(y, M + 1, R, k - ct[x]));
} lnl findsum(int x) {return findsum(0, 0, n-1, x);}
void build(vector<lnl>& v) {
val = v; sort(all(val)); val.resize(unique(all(val)) - val.begin());
n = val.size(); sum.resize(4*n+1, 0); ct.resize(4*n+1, 0);
for (int i: v) update(i, 1);
}
};
vector<Tree> t;
void dfs(int u, int p, int wp, int mx) {
vis[u] = 1; dp[u][0] = 0; dp[u][1] = wp;
for (int j = 0; j < 2; j++) {
int ct = adj[u].size() - mx - j; vector<lnl> add;
for (auto i: cur[u]) {
int v = i.F, w = i.S;
if (v == p) continue;
if (!vis[v]) dfs(v, u, w, mx);
dp[u][j] += min(dp[v][0], dp[v][1]);
if (dp[v][1] < dp[v][0]) ct--;
else add.pb(dp[v][1] - dp[v][0]);
}
if (ct <= 0) continue; sort(all(add));
for (int i = 0; i < add.size() && ct; i++) {
if (add[i] < t[u].find(ct)) {dp[u][j] += add[i]; ct--;}
else break ;
}
if (ct) dp[u][j] += t[u].findsum(ct);
}
}
vector<lnl> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < N - 1; i++) {
adj[U[i]].pb({V[i], W[i]});
adj[V[i]].pb({U[i], W[i]});
}
for (int i = 0; i < N; i++) {deg[adj[i].size()-1].pb(i);}
vector<int> nodes;
vector<lnl> ans(N, 0);
t.resize(N);
for (int i = 0; i < N; i++) {
vector<lnl> val;
for (auto l: adj[i]) val.pb((lnl)l.S);
t[i].build(val);
}
for (int i = N - 1; i >= 0; i--) {
for (int u: deg[i]) {
for (auto i: adj[u]) {
cur[i.F].pb({u, i.S});
t[i.F].update(i.S, -1);
}
nodes.pb(u);
}
for (int u: nodes) {if (vis[u]) continue; dfs(u, -1, 0, i); ans[i] += dp[u][0];}
for (int u: nodes) {vis[u] = 0;}
}
return ans;
}
//ED
