#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define inf 1000000000000
const int MXN = 1e5 + 5;
struct BIT
{
int n;
vector<long long> ft;
void init(int N)
{
n = N + 5;
ft.assign(n + 5, 0);
}
void add(int pos, long long val)
{
for (; pos <= n; pos += pos & -pos) ft[pos] += 1LL * val;
}
long long get(int pos, long long res = 0)
{
for (; pos > 0; pos -= pos & -pos) res += ft[pos];
return res;
}
};
int n, K;
vector<array<long long, 2>> adj[MXN];
set<array<long long, 2>> g[MXN];
int used[MXN];
BIT cnt[MXN], sum[MXN];
void unlock(int node, int idx)
{
cnt[node].add(idx + 1, 1);
sum[node].add(idx + 1, adj[node][idx][0]);
}
long long sumk(int node, int k)
{
if (k < 0) return -inf;
int sz = adj[node].size();
long long cur = 0, curs = 0;
for (int i = 20; i >= 0; i--)
{
if ((cur | (1 << i)) > sz) continue;
if (cnt[node].ft[cur | (1 << i)] <= k)
{
k -= cnt[node].ft[cur | (1 << i)];
curs += sum[node].ft[cur | (1 << i)];
cur |= (1 << i);
}
}
return curs;
}
array<long long, 2> dfs(int a)
{
used[a] = 1;
array<long long, 2> res = {0, 0};
long long S = 0;
vector<long long> o;
for (auto [w, v] : g[a])
{
if (used[v]) continue;
array<long long, 2> x = dfs(v);
S += x[0];
o.push_back(x[1] + w - x[0]);
}
sort(o.rbegin(), o.rend());
res[0] = sumk(a, K) + S, res[1] = sumk(a, K - 1) + S;
long long cnt = K, curS = 0;
for (long long &val : o)
{
curS += val;
cnt--;
res[0] = max(res[0], S + curS + sumk(a, cnt));
res[1] = max(res[1], S + curS + sumk(a, cnt - 1));
}
return res;
}
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W)
{
n = N;
long long all = 0;
for (int i = 0; i < U.size(); i++)
{
long long u = U[i], v = V[i], w = W[i];
adj[u].push_back({w, v});
adj[v].push_back({w, u});
g[u].insert({w, v});
g[v].insert({w, u});
all += w;
}
for (int i = 0; i < N; i++)
{
sort(adj[i].rbegin(), adj[i].rend());
}
for (int i = 0; i < N; i++)
{
cnt[i].init(adj[i].size());
sum[i].init(adj[i].size());
}
vector<array<long long, 2>> ed;
vector<array<long long, 5>> q;
for (int i = 0; i < U.size(); i++)
{
long long u = U[i], v = V[i], w = W[i];
if (adj[u].size() > adj[v].size()) swap(u, v);
ed.push_back({(long long)adj[v].size(), w});
int lx = 0, rx = (int)adj[v].size() - 1;
while (lx < rx)
{
int mid = (lx + rx) >> 1;
if (adj[v][mid] > array<long long, 2>{w, u}) lx = mid + 1;
else rx = mid;
}
q.push_back({(long long)adj[u].size(), u, v, w, lx});
}
sort(ed.begin(), ed.end());
sort(q.begin(), q.end());
int o[n];
iota(o, o + n, 0);
sort(o, o + n, [&](int x, int y)
{
return adj[x].size() > adj[y].size();
});
vector<long long> ans;
for (long long k = 0, i = 0, j = 0, alr = 0; k < n; k++)
{
K = k;
while (i < ed.size() && ed[i][0] <= k) alr += ed[i][1], i++;
while (j < q.size() && q[j][0] <= k)
{
int u = q[j][1], v = q[j][2], w = q[j][3], idx = q[j][4];
unlock(v, idx);
g[v].erase({w, u});
j++;
}
long long res = 0;
for (int &i : o)
{
if (adj[i].size() <= k) break;
used[i] = 0;
}
for (int &i : o)
{
if (adj[i].size() <= k) break;
if (used[i]) continue;
array<long long, 2> x = dfs(i);
res += max(x[0], x[1]);
}
ans.push_back(all - (res + alr));
}
return ans;
}
