#include <stdlib.h>
#include <time.h>
#include <string>
#define assert(x) if(!(x))__builtin_trap()
#define NN 100000
#define MM (2*NN)
#define PL (1<<23)
int L[PL], R[PL], S[PL], cur, P[PL];
long long Sum[PL], K[PL];
int node(long long key) {
int p = ++cur;
Sum[p] = K[p] = key;
L[p] = R[p] = 0;
S[p] = 1;
P[p] = rand();
return p;
}
void pul(int v) {
if (v) {
S[v] = S[L[v]] + S[R[v]] + 1;
Sum[v] = K[v] + Sum[L[v]] + Sum[R[v]];
}
}
void merge(int *v, int l, int r) {
if (l == 0 || r == 0) {
*v = l ^ r;
return;
} else if (P[l] < P[r]) {
merge(L+r, l, L[r]);
*v = r;
} else {
merge(R+l, R[l], r);
*v = l;
}
pul(*v);
}
void split(int v, int *l, int *r, long long key) {
if (!v)
*l = 0, *r = 0;
else if (K[v] <= key)
split(R[v], R+v, r, key), *l = v;
else
split(L[v], l, L+v, key), *r = v;
pul(v);
}
void spliti(int v, int *l, int *r, int sz) {
if (!v)
*l = 0, *r = 0;
else if (S[L[v]] < sz)
spliti(R[v], R+v, r, sz - 1 - S[L[v]]), *l = v;
else
spliti(L[v], l, L+v, sz), *r = v;
pul(v);
}
void add(int *v, long long key)
{
int t1, t2, t3, t4;
split(*v, &t2, &t3, key);
split(t2, &t1, &t2, key - 1);
merge(&t2, t2, node(key));
merge(&t4, t1, t2);
merge(v, t4, t3);
}
void remove(int *v, long long key) {
int t1, t2, t3, t4, t5;
split(*v, &t2, &t3, key);
split(t2, &t1, &t2, key - 1);
spliti(t2, &t4, &t5, 1);
merge(&t1, t1, t5);
merge(v, t1, t3);
}
long long min_k_sum(int *v, int k) {
if (k >= S[*v])
return Sum[*v];
int t1, t2;
spliti(*v, &t1, &t2, k);
long long zz = Sum[t1];
merge(v, t1, t2);
return zz;
}
#include "roads.h"
#include <vector>
long long dp_loose[NN], dp_tight[NN], delsum[NN];
int deg[NN], heap[NN], time_visited[NN];
#include<set>
#include<utility>
std::set<std::pair<int, int> > gg[NN];
void forest_remove(int i) {
for (auto [w, j] : gg[i]) {
delsum[j] += w;
add(heap + j, -w);
gg[j].erase(std::make_pair(w, i));
}
}
void dfs(int u, int p, int k) {
long long base;
time_visited[u] = k;
for (auto [w, v] : gg[u])
if (v != p)
dfs(v, u, k);
base = delsum[u];
for (auto [w, v] : gg[u]) if (v != p) {
base += w + dp_tight[v];
long long xx = dp_loose[v] - w - dp_tight[v];
if (xx <= 0)
add(heap + u, xx);
}
dp_tight[u] = base + min_k_sum(heap+u, k);
dp_loose[u] = base + min_k_sum(heap+u, k - 1);
for (auto [w, v] : gg[u]) {
long long xx = dp_loose[v] - w - dp_tight[v];
if (xx <= 0)
remove(heap + u, xx);
}
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
srand(time(0));
int i, k, ii;
std::vector<long long> ans(N);
for (i = 0; i < N - 1; ++i) {
++deg[U[i]], ++deg[V[i]];
gg[U[i]].emplace(W[i], V[i]);
gg[V[i]].emplace(W[i], U[i]);
}
std::set<int> interesting;
std::vector<std::basic_string<int> > eh(N);
for (i = 0; i < N; ++i) {
time_visited[i] = -1;
eh[deg[i]].push_back(i);
interesting.insert(i);
}
for (k = 0; k < N; ++k) {
for (auto ii : eh[k]) {
forest_remove(ii);
interesting.erase(ii);
}
for (auto ii : interesting)
if (time_visited[ii] != k) {
dfs(ii, -1, k);
ans[k] += dp_tight[ii];
}
}
return ans;
}
/*
* sum deg(v) = 2m = 2n-2
*
* let f(x) = count of vertices with degree >= x
*
* Lemma:
* sum f(x) for all x in [0..n-1] = sum deg(v) = 2m
*
* Proof:
* - Contribution of node u to sum f(x) is deg(u)
*
* for each edge (u, v), degree u and v increases by one
* subsequently, each edge contribute two to sum f(x)
*
*
*
* N = 100000:
* sort vertices by deg
*
* maintain induced subgraph of vertices with deg >= k for each k
* do dp on the forest, need to maintain heap of edges connecting node going outside the forest too
*/
