#include<bits/stdc++.h>
#include "roads.h"
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii > vii;
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
const int N=1e5+5;
vii E[N], E2[N];
ll dp[N][2];
int par[N];
int vis[N];
vi co[N];
vector<ll> suf[N];
void dfs(int v, int k){
for(pii e:E[v]){
int u=e.st, c=e.nd;
if(u!=par[v]){
par[u]=v;
dfs(u, k);
}
}
dp[v][1]=dp[v][0]=0;
vector<int> V;
for(pii e:E[v]){
int u=e.st, c=e.nd;
if(u!=par[v]){
dp[v][0]+=dp[u][1];
V.pb(dp[u][0]+c-dp[u][1]);
}
}
sort(all(V));
for(int j=V.size()-1; j>=int(V.size())-k+1 && j>=0 && V[j]>0; j--){
dp[v][0]+=V[j];
}
dp[v][1]=dp[v][0];
if(V.size()>=k && V.end()[-k]>0)dp[v][1]+=V.end()[-k];
//if(i>=2)assert(2*dp[v][1][i-1]>=dp[v][1][i]+dp[v][1][i-2]);
//deb(v, dp[v][0], dp[v][1], dp[v][2]);
}
void dfs2(int v, int k){
for(pii e:E2[v])dfs2(e.st, k);
dp[v][1]=dp[v][0]=0;
vector<int> V;
for(pii e:E2[v]){
int u=e.st, c=e.nd;
dp[v][0]+=dp[u][1];
V.pb(dp[u][0]+c-dp[u][1]);
}
sort(all(V));
ll s=0;
ll opt=0, opt2=0;
dp[v][1]=dp[v][0];
/*for(int i:V){
deb(i);
}
deb(" ");
for(int i:suf[v]){
deb(i);
}*/
if(suf[v].size()){
for(int j=0; j<=V.size(); j++){
if(j+1<k){
opt=max(opt, suf[v].end()[max(-k+1+j, -int(suf[v].size()))]+s);
//deb(j, s, suf[v].end()[-k+1+j]);
}
if(j<k)opt2=max(opt2, suf[v].end()[max(-k+j, -int(suf[v].size()))]+s);
if(j!=V.size())s+=V.end()[-1-j];
}
}
else{
for(int j=0; j<=k && j<=V.size(); j++){
if(j+1<=k){
opt=max(opt,s);
//deb(j, s, suf[v].end()[-k+1+j]);
}
if(j<=k)opt2=max(opt2, s);
if(j!=V.size())s+=V.end()[-1-j];
}
}
opt2=max(opt, opt2);
dp[v][0]+=opt;
dp[v][1]+=opt2;
//deb(v, dp[v][0], dp[v][1]);
}
std::vector<long long> minimum_closure_costs(int n, std::vector<int> uu,
std::vector<int> vv,std::vector<int> ww) {
ll sum=0;
for(int i=0; i<n-1; i++){
E[uu[i]].eb(vv[i], ww[i]);
E[vv[i]].eb(uu[i], ww[i]);
sum+=ww[i];
}
vector<ll> ans(n);
ans[0]=sum;
par[0]=-1;
int K=100;
for(int i=1; i<K && i<n; i++){
dfs(0, i);
ans[i]=sum-dp[0][1];
}
for(int t=K; t<n; t++){
if(t%100==0 && t<=1000){
vi todo;
sum=0;
for(int i=0; i<n; i++){
if(E[i].size()>=K){
E2[i].clear();
suf[i].clear();
co[i].clear();
if(i==0 || E[par[i]].size()<K)todo.pb(i);
for(auto e:E[i]){
if(E[e.st].size()>=K && e.st!=par[i]){
//deb(i, par[i], e.st);
E2[i].pb(e);
}
if(E[e.st].size()<K || e.st!=par[i]){
sum+=e.nd;
if(E[e.st].size()<K){
co[i].pb(e.nd);
}
}
}
if(co[i].size())sort(all(co[i]));
suf[i].resize(co[i].size());
for(int j=int(co[i].size())-1; j>=0; j--){
suf[i][j]=co[i][j];
if(j!=co[i].size()-1){
suf[i][j]+=suf[i][j+1];
}
}
}
}
}
ans[t]=sum;
for(int v:todo){
dfs2(v, t);
ans[t]-=dp[v][1];
}
}
return ans;
}
Compilation message
roads.cpp: In function 'void dfs(int, int)':
roads.cpp:32:15: warning: unused variable 'c' [-Wunused-variable]
32 | int u=e.st, c=e.nd;
| ^
roads.cpp:52:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
52 | if(V.size()>=k && V.end()[-k]>0)dp[v][1]+=V.end()[-k];
| ~~~~~~~~^~~
roads.cpp: In function 'void dfs2(int, int)':
roads.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int j=0; j<=V.size(); j++){
| ~^~~~~~~~~~
roads.cpp:83:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | if(j!=V.size())s+=V.end()[-1-j];
| ~^~~~~~~~~~
roads.cpp:87:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int j=0; j<=k && j<=V.size(); j++){
| ~^~~~~~~~~~
roads.cpp:93:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | if(j!=V.size())s+=V.end()[-1-j];
| ~^~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:123:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
123 | if(E[i].size()>=K){
| ~~~~~~~~~~~^~~
roads.cpp:127:33: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
127 | if(i==0 || E[par[i]].size()<K)todo.pb(i);
| ~~~~~~~~~~~~~~~~^~
roads.cpp:129:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
129 | if(E[e.st].size()>=K && e.st!=par[i]){
| ~~~~~~~~~~~~~~^~~
roads.cpp:133:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
133 | if(E[e.st].size()<K || e.st!=par[i]){
| ~~~~~~~~~~~~~~^~
roads.cpp:135:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
135 | if(E[e.st].size()<K){
| ~~~~~~~~~~~~~~^~
roads.cpp:144:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | if(j!=co[i].size()-1){
| ~^~~~~~~~~~~~~~~~
roads.cpp:152:15: error: 'todo' was not declared in this scope
152 | for(int v:todo){
| ^~~~
