#include<bits/stdc++.h> #include "roads.h" using namespace std; const int maxn=100000+10; struct yal{ int u,v,w; int getad(int fu){ int ret=(u^v^fu); return ret; } }; long long sum=0; yal alled[maxn]; vector<int>adj[maxn],fake[maxn]; set<int>allrishe; int n,vis[maxn],len[maxn],par[maxn]; long long dp0[maxn],dp1[maxn],fdp0[maxn],fdp1[maxn]; set<pair<int,int>>st[maxn],sta[maxn]; set<pair<int,int>>sortlen; void aval(int u,int lena,int para=-1){ par[u]=para; len[u]=lena; for(auto xx:adj[u]){ int x=alled[xx].getad(u); if(xx!=para){ fake[u].push_back(xx); aval(x,lena+1,xx); } } } void del(int u){ vis[u]=1; sortlen.erase(make_pair(-len[u],u)); allrishe.erase(u); if(u!=0){ st[alled[par[u]].getad(u)].erase(make_pair(dp1[u]-dp0[u],u)); sta[alled[par[u]].getad(u)].erase(make_pair(dp1[u]-dp0[u],u)); dp0[alled[par[u]].getad(u)]-=dp1[u]-dp0[u]; sta[alled[par[u]].getad(u)].insert(make_pair(alled[par[u]].w,u)); //cout<<u<<" "<<alled[par[u]].getad(u)<<" "<<alled[par[u]].w<<"\n"; } // cout<<u<<"wtf "<<(int)fake[u].size()<<"\n"; for(auto xx:fake[u]){ int x=alled[xx].getad(u); // cout<<x<<" "<<u<<" "<<vis[x]<<"\n"; if(vis[x]==0){ allrishe.insert(x); } } for(auto xx:adj[u]){ int x=alled[xx].getad(u); if(vis[x]==1){ sum-=alled[xx].w; } } } void upd(int u,int i){ if(u!=0){ dp0[alled[par[u]].getad(u)]-=fdp0[u]; dp1[alled[par[u]].getad(u)]-=fdp0[u]; long long z=fdp1[u]-fdp0[u]; st[alled[par[u]].getad(u)].erase(make_pair(z,u)); sta[alled[par[u]].getad(u)].erase(make_pair(z,u)); } // cout<<u<<" asd "<<i<<" "<<(*sta[u].rbegin()).first<<" "<<(int)sta[u].size()<<" "<<(int)st[u].size()<<"\n"; while((int)sta[u].size()>0&&(int)st[u].size()<i&&(*sta[u].rbegin()).first>0){ auto x=*sta[u].rbegin(); sta[u].erase(x); st[u].insert(x); dp0[u]+=x.first; // cout<<u<<" wtf "<<x.first<<"\n"; } if(u!=0&&(int)st[u].size()==i){ dp1[u]=dp0[u]-(*st[u].begin()).first+alled[par[u]].w; } else if(u==0){ dp1[u]=dp0[u]; } else{ dp1[u]=dp0[u]+alled[par[u]].w; } if(u!=0){ sta[alled[par[u]].getad(u)].insert(make_pair(dp1[u]-dp0[u],u)); dp0[alled[par[u]].getad(u)]+=dp0[u]; dp1[alled[par[u]].getad(u)]+=dp0[u]; } //cout<<u<<" "<<dp0[u]<<" "<<dp1[u]<<"\n"; return ; } std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,std::vector<int> V,std::vector<int> W){ n=N; for(int i=0;i<n-1;i++){ alled[i].u=U[i]; alled[i].v=V[i]; alled[i].w=W[i]; adj[alled[i].u].push_back(i); adj[alled[i].v].push_back(i); sum+=alled[i].w; } allrishe.insert(0); aval(0,0); // cout<<"salam"<<endl; vector<pair<int,int>>v; for(int i=0;i<n;i++){ v.push_back(make_pair((int)adj[i].size(),i)); sortlen.insert(make_pair(-len[i],i)); } sort(v.rbegin(),v.rend()); vector<long long>res(n); res[0]=sum; for(int i=1;i<=n-1;i++){ //cout<<i<<endl; while((int)v.size()>0&&v.back().first<=i){ //cout<<"in j "<<j<<endl; del(v.back().second); v.pop_back(); //cout<<"out j "<<j<<endl; } for(auto h:sortlen){ // cout<<"in h "<<h<<endl; //cout<<i<<" "<<h.second<<'\n'; upd(h.second,i); fdp0[h.second]=dp0[h.second]; fdp1[h.second]=dp1[h.second]; } res[i]=sum; // cout<<i<<" asd "<<(int)allrishe.size()<<"\n"; for(auto x:allrishe){ // cout<<x<<" "<<dp0[x]<<" "<<dp1[x]<<endl; if(x==0){ res[i]-=dp0[x]; } else{ res[i]-=max(dp0[x],dp1[x]); } } } return res; }