#include<bits/stdc++.h> #include "roads.h" using namespace std; const long long maxn=100000+10; struct yal{ long long u,v,w; long long getad(long long fu){ long long ret=(u^v^fu); return ret; } }; long long sum=0; yal alled[maxn]; vector<long long>adj[maxn],fake[maxn]; set<long long>allrishe; long long n,vis[maxn],len[maxn],par[maxn]; long long dp0[maxn],dp1[maxn],fdp0[maxn],fdp1[maxn]; set<pair<long long,long long>>st[maxn],sta[maxn]; set<pair<long long,long long>>sortlen; void aval(long long u,long long lena,long long para=-1){ par[u]=para; len[u]=lena; for(auto xx:adj[u]){ long long x=alled[xx].getad(u); if(xx!=para){ fake[u].push_back(xx); aval(x,lena+1,xx); } } } void del(long long u,int i){ vis[u]=1; sortlen.erase(make_pair(-len[u],u)); allrishe.erase(u); if(u!=0){ if(st[alled[par[u]].getad(u)].count(make_pair(fdp1[u]-fdp0[u],u))!=0){ dp0[alled[par[u]].getad(u)]-=fdp1[u]-fdp0[u]; if((int)st[alled[par[u]].getad(u)].size()==i&&(*st[alled[par[u]].getad(u)].begin())==make_pair(fdp1[u]-fdp0[u],u)){ dp1[alled[par[u]].getad(u)]-=fdp1[u]-fdp0[u]; } } dp0[alled[par[u]].getad(u)]-=fdp0[u]; dp1[alled[par[u]].getad(u)]-=fdp0[u]; st[alled[par[u]].getad(u)].erase(make_pair(fdp1[u]-fdp0[u],u)); sta[alled[par[u]].getad(u)].erase(make_pair(fdp1[u]-fdp0[u],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 "<<(long long)fake[u].size()<<"\n"; for(auto xx:fake[u]){ long long x=alled[xx].getad(u); // cout<<x<<" "<<u<<" "<<vis[x]<<"\n"; if(vis[x]==0){ allrishe.insert(x); } } for(auto xx:adj[u]){ long long x=alled[xx].getad(u); if(vis[x]==1){ sum-=alled[xx].w; } } } void upd(long long u,long long 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<<" "<<(long long)sta[u].size()<<" "<<(long long)st[u].size()<<"\n"; while((long long)sta[u].size()>0&&(long long)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&&(long long)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(long long 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<long long,long long>>v; for(long long i=0;i<n;i++){ v.push_back(make_pair((long long)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(long long i=1;i<=n-1;i++){ //cout<<i<<endl; while((long long)v.size()>0&&v.back().first<=i){ //cout<<"in j "<<j<<endl; del(v.back().second,i); 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 "<<(long long)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; }