#include <bits/stdc++.h>
using namespace std;
#include "roads.h"
struct ksum {
multiset<long long> A,B; int n; long long sum;
ksum(int k = 0) : A(),B(),n(k),sum(0) {}
void add(long long x){
if (A.size()<n||(!A.empty()&&*A.rbegin()>x)||x<0) A.emplace(x),sum += x;
else B.emplace(x);
while(A.size()>n&&*A.rbegin()>=0){
sum -= *A.rbegin(),B.emplace(*A.rbegin()),A.erase(prev(A.end()));
}
}
void del(long long x){
if (!A.empty()&&*A.rbegin()>=x) A.erase(A.find(x)),sum -= x;
else B.erase(B.find(x));
while(A.size()<n&&!B.empty()) sum += *B.begin(),A.emplace(*B.begin()),B.erase(B.begin());
}
long long increase(){
++n;
while(A.size()<n&&!B.empty()) sum += *B.begin(),A.emplace(*B.begin()),B.erase(B.begin());
return sum;
}
};
vector<long long> minimum_closure_costs(int n,vector<int> U,vector<int> V,vector<int> W){
vector<vector<pair<int,int>>> G(n);
vector<int> P(n),A(n),D(n),O(n,n);
for (int i(0);i < n-1;++i) G[U[i]].emplace_back(V[i],W[i]),G[V[i]].emplace_back(U[i],W[i]);
auto dfs = [&](auto& dfs,int x,int p,int d) -> void {
D[x] = d,P[x] = p;
for (auto [a,b]:G[x]) if (a!=p) dfs(dfs,a,x,d+1);
};
dfs(dfs,0,-1,0);
multiset<pair<int,int>,greater<pair<int,int>>> M;
for (int i(0);i < n;++i) M.emplace(G[i].size()-1,i);
vector<ksum> S(n);
multiset<pair<int,int>> L;
vector<vector<pair<int,int>>> H(n);
auto dp = [&](auto& dp,int x,int y) -> pair<long long,long long> {
O[x] = y;
long long s = 0;
vector<long long> T;
for (auto [i,w]:H[x]){
auto [a,b] = dp(dp,i,y);
s += b,T.emplace_back(a+w-b),S[x].add(T.back());
}
long long t = S[x].sum;
pair<long long,long long> ret(s+t,s+S[x].increase());
//cout << x << ' ' << y << ' ' << s << ' ' << ret.first << ' ' << ret.second << endl;
for (long long a:T) S[x].del(a);
return ret;
};
vector<long long> ret;
for (int i(n-1);i > -1;--i){
while(!M.empty()&&M.begin()->first==i){
auto [a,b] = *M.begin(); M.erase(M.begin());
for (auto [c,d]:G[b]){
if (A[c]==1){
S[c].del(d);
if (c==P[b]) H[c].emplace_back(b,d);
else H[b].emplace_back(c,d);
} else S[b].add(d);
}
A[b] = 1,L.emplace(D[b],b);
}
long long res(0);
for (auto [w,k]:L) if (O[k]!=i) res += dp(dp,k,i).second;
ret.emplace_back(res);
}
reverse(ret.begin(),ret.end());
return ret;
}
