#include <bits/stdc++.h>
using namespace std;
const long long oo = 1LL << 60;
int n, preDfs[100100], postDfs[100100], dfsTime, deg[100100], curDeg[100100], par[100100];
vector<pair<int, int>> a[100100];
long long f[100100];
long long g[100100]; // can keep parent edge
vector<int> nodes[100100];
void visit(int x, int k)
{
f[x] = 0;
vector<long long> gain;
for (auto [y, w] : a[x])
if (y != par[x])
{
visit(y, k);
f[x] += f[y] + w;
gain.push_back(g[y] - f[y] - w);
}
sort(gain.begin(), gain.end());
g[x] = f[x];
for (int i = 0; i < k && i < gain.size(); i++)
{
if (gain[i] >= 0)
break;
f[x] += gain[i];
if (i < k - 1)
g[x] += gain[i];
}
f[x] = min(f[x], g[x]);
}
void dfs(int x)
{
preDfs[x] = ++dfsTime;
for (auto [y, _] : a[x])
if (y != par[x])
{
par[y] = x;
dfs(y);
}
postDfs[x] = dfsTime;
}
int solve(int k, set<pair<int, int>> &nodes)
{
for (auto [_, x] : nodes)
curDeg[x] = deg[x];
int res = 0;
for (auto [_, x] : nodes)
if (curDeg[x] > k)
{
res += curDeg[x] - k;
if (par[x] >= 0)
curDeg[par[x]]--;
}
return res;
}
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
n = N;
int isLine = 1, isWeighted = 0;
for (int i = 0; i < n - 1; i++)
{
a[U[i]].push_back({V[i], W[i]});
a[V[i]].push_back({U[i], W[i]});
if (U[i] != i || V[i] != i + 1)
isLine = 0;
deg[U[i]]++;
deg[V[i]]++;
if (W[i] > 1)
isWeighted = 1;
}
for (int i = 0; i < n; i++)
nodes[deg[i]].push_back(i);
vector<long long> ans(n);
ans[0] = accumulate(W.begin(), W.end(), 0LL);
dfsTime = 0;
par[0] = -1;
dfs(0);
// 1
if (a[0].size() == n - 1)
{
sort(W.begin(), W.end(), greater<int>());
for (int i = n - 2; i >= 0; i--)
ans[i] = ans[i + 1] + W[i];
return ans;
}
// 2
if (isLine)
{
vector<long long> f(n, oo);
f[0] = 0;
f[1] = W[0];
for (int i = 2; i < n; i++)
f[i] = min(f[i - 1], f[i - 2]) + W[i - 1];
ans[1] = min(f[n - 1], f[n - 2]);
}
if (n <= 2000)
{
for (int i = 1; i < n - 1; i++)
{
visit(0, i);
ans[i] = f[0];
}
}
else if (!isWeighted)
{
set<pair<int, int>> s;
for (int i = 0; i < n; i++)
s.insert({-preDfs[i], i});
for (int i = 1; i < n - 1; i++)
{
for (int x : nodes[i])
s.erase({-preDfs[x], x});
ans[i] = solve(i, s);
}
}
return ans;
}
