#include "roads.h"
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define ll long long
#define pii pair<ll, ll>
#define ppi pair<pii, ll>
#define fst first
#define snd second
using namespace std;
vector<pii> adj[100001];
vector<ll> temp;
namespace BIT
{
vector<ll> C;
ll BIT[100001][2];
inline void reset()
{
for (int i = 0; i <= C.size(); i++) {BIT[i][0] = BIT[i][1] = 0;}
C.clear();
}
inline void pushPoint(ll x) {C.push_back(x);}
inline void process() {sort(C.begin(), C.end()); C.resize(unique(C.begin(), C.end()) - C.begin());}
inline ll query(int t, ll x)
{
x = upper_bound(C.begin(), C.end(), x) - C.begin();
ll ret = 0;
for (; x; x -= x & (-x)) {ret += BIT[x][t];}
return ret;
}
inline ll query2(int t, ll x)
{
ll ret = 0;
for (; x; x -= x & (-x)) {ret += BIT[x][t];}
return ret;
}
inline void update(int t, int x, ll v)
{
x = upper_bound(C.begin(), C.end(), x) - C.begin();
//cerr << "UPD: " << t << " " << x << " " << v << "\n";
for (; x <= C.size(); x += x & (-x)) {BIT[x][t] += v;}
}
inline ll findKth(int x)
{
int L = 1, R = C.size() + 1;
while (L < R)
{
int M = L + R >> 1;
if (query2(0, M) < x) {L = M + 1;}
else {R = M;}
}
if (L == C.size() + 1) {return query2(1, C.size());}
else {return query2(1, L - 1) + C[L - 1] * (x - query2(0, L - 1));}
}
}
struct DS {vector<pii> DP; int fix = 0;};
inline bool comp(const pair<DS*, int> L, const pair<DS*, int> R)
{
return L.fst -> DP.size() > R.fst -> DP.size();
}
DS* DFS(int u, int p)
{
vector<pair<DS*, int>> child;
for (const auto &v : adj[u])
{
if (v.fst == p) continue;
child.push_back({DFS(v.fst, u), v.snd});
}
int deg = adj[u].size();
if (child.size())
{
BIT :: reset();
for (const auto &v : adj[u])
{
if (v.fst == p) continue;
BIT :: pushPoint(-v.snd);
}
BIT :: process();
sort(child.begin(), child.end(), comp);
while (child[0].fst -> DP.size() < deg) child[0].fst -> DP.push_back({0, 0});
for (int j = child[0].fst -> fix; j < deg; j++) {child[0].fst -> DP[j].fst = child[0].fst -> DP[j].snd;}
for (int j = deg; j < child[0].fst -> fix; j++) {child[0].fst -> DP[j].snd = min(child[0].fst -> DP[j].snd, child[0].fst -> DP[j].fst + child[0].snd);}
child[0].fst -> fix = deg;
//cerr << "DFS: " << u << " " << child.size() << '\n';
int jj = child.size() - 1; ll tp = 0;
for (int i = 0; i < deg; i++)
{
vector<ll> V; ll t = 0;
for (; jj >= 0 && child[jj].fst -> DP.size() <= i; jj--)
{
//cerr << "jj: " << jj << "\n";
tp += child[jj].snd;
BIT :: update(0, -child[jj].snd, 1);
BIT :: update(1, -child[jj].snd, -child[jj].snd);
}
t = tp;
for (int j = 0; j <= jj; j++)
{
if (i >= child[j].fst -> fix) {child[j].fst -> DP[i].fst = child[j].fst -> DP[i].snd;}
t += child[j].fst -> DP[i].fst + child[j].snd;
V.push_back(child[j].fst -> DP[i].snd - (child[j].fst -> DP[i].fst + child[j].snd));
if (V.back() >= 0) {V.pop_back();}
}
//cerr << i << ": " << t << " " << jj << '\n';
sort(V.begin(), V.end());
child[0].fst -> DP[i].fst = child[0].fst -> DP[i].snd = t;
int j = 0;
for (j = 0; j < V.size(); j++)
{
if (BIT :: query(0, V[j]) + (j + 1) <= i + 1) {child[0].fst -> DP[i].fst += V[j];}
else {break;}
}
//cerr << j << " " << i + 1 - j << " " << BIT :: findKth(i + 1 - j) << "\n";
child[0].fst -> DP[i].fst += BIT :: findKth(i + 1 - j);
j = 0;
for (j = 0; j < V.size(); j++)
{
if (BIT :: query(0, V[j]) + (j + 1) <= i) {child[0].fst -> DP[i].snd += V[j];}
else {break;}
}
//cerr << j << " " << i - j << " " << BIT :: findKth(i - j) << "\n";
child[0].fst -> DP[i].snd += BIT :: findKth(i - j);
}
for (int j = 1; j < child.size(); j++)
{
for (int k = deg; k < child[j].fst -> DP.size(); k++)
{
if (k < child[j].fst -> fix) child[0].fst -> DP[k].snd += min(child[j].fst -> DP[k].fst + child[j].snd, child[j].fst -> DP[k].snd);
else child[0].fst -> DP[k].snd += child[j].fst -> DP[k].snd;
}
}
/*cerr << "DFS: " << u << " " << child[0].fst -> fix << "\n";
for (int i = 0; i < child[0].fst -> DP.size(); i++)
{
cerr << child[0].fst -> DP[i].fst << " " << child[0].fst -> DP[i].snd << "\n";
}*/
return child[0].fst;
}
else {return new DS;}
}
vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W)
{
vector<ll> ret(N);
for (int i = 1; i < N; i++)
{
ret[0] += W[i - 1];
adj[U[i - 1]].push_back({V[i - 1], W[i - 1]});
adj[V[i - 1]].push_back({U[i - 1], W[i - 1]});
}
DS* ans = DFS(0, -1);
for (int i = 0; i < ans -> DP.size(); i++)
{
if (i < ans -> fix) ret[i + 1] = ans -> DP[i].fst;
else ret[i + 1] = ans -> DP[i].snd;
}
return ret;
}
