This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#ifndef SKY
#include "roads.h"
#endif // SKY
using namespace std;
#define N 100010
#define ll long long
#define fs first
#define sc second
#define ii pair<ll,int>
#define pb push_back
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("omit-frame-pointer")
#pragma GCC optimize("unroll-loops")
const ll MAX_VAL=2e14;
int cnt,k,n,ktr[N],spec[N];
vector<ii>g[N],edge[N];
ll tong,them,cost[N],dp[N][2];
vector<ll>sum[N];
vector<int>lis,ds[N];
struct nho
{
void build(int u,int p)
{
for(auto v:g[u])
if(v.sc!=p)
{
build(v.sc,u);
cost[v.sc]=v.fs;
}
}
ll solve(int u,int p,int sl,const vector<ll>&s)
{
if(sl<0)
return MAX_VAL;
ll res=0;
for(auto v:g[u])
if(v.sc!=p)
if(dp[v.sc][0]<=dp[v.sc][1])
{
res+=dp[v.sc][0];
}else
{
res+=dp[v.sc][1];
}
for(int i=0;i<(int)s.size()-sl;i++)
res+=s[i];
return res;
}
void DFS(int u,int p)
{
for(auto v:g[u])
if(v.sc!=p)
DFS(v.sc,u);
vector<ll>s;
for(auto v:g[u])
if(v.sc!=p&&dp[v.sc][0]>dp[v.sc][1])
s.pb(dp[v.sc][0]-dp[v.sc][1]);
sort(s.begin(),s.end());
//0
dp[u][0]=solve(u,p,k,s)+cost[u];
//1
dp[u][1]=solve(u,p,k-(u!=0),s);
}
}nho;
ll get(int u,int sl)
{
if(sl>=sum[u].size())
return 0;
if(sl==0)
return sum[u].back();
return sum[u].back()-sum[u][sl-1];
}
ll solve(int u,int p,int sl,const vector<ll>&s)
{
if(sl<0)
return MAX_VAL;
ll cong=0,res=MAX_VAL;
for(auto v:edge[u])
if(v.sc!=p)
{
if(dp[v.sc][0]<=dp[v.sc][1])
{
cong+=dp[v.sc][0];
}else
{
cong+=dp[v.sc][1];
}
}
if((int)s.size()<=sl)
res=min(res,cong+get(u,sl-(int)s.size()));
for(int i=0;i<s.size();i++)
{
cong+=s[i];
if((int)s.size()-i-1<=sl)
res=min(res,cong+get(u,sl-((int)s.size()-i-1)));
}
return res;
}
void DFS(int u,int p)
{
ktr[u]=k;
for(auto v:edge[u])
if(v.sc!=p)
{
cost[v.sc]=v.fs;
DFS(v.sc,u);
}
vector<ll>s;
for(auto v:edge[u])
if(v.sc!=p&&dp[v.sc][0]>dp[v.sc][1])
s.pb(dp[v.sc][0]-dp[v.sc][1]);
sort(s.begin(),s.end());
//0
dp[u][0]=solve(u,p,k,s)+cost[u];
//1
dp[u][1]=solve(u,p,k-(p!=-1),s);
}
vector<long long> minimum_closure_costs(int NNN, vector<int> UUU, vector<int> VVV, vector<int> WWW)
{
n=NNN;
for(int i=0;i<n-1;i++)
{
int u=UUU[i],v=VVV[i],w=WWW[i];
g[u].pb({w,v});
g[v].pb({w,u});
}
cost[0]=1e18;
nho.build(0,-1);
vector<ll>kq;
for(k=0;k<=0;k++)
{
nho.DFS(0,-1);
kq.pb(dp[0][1]);
}
for(int i=0;i<n;i++)
ds[(int)g[i].size()].pb(i);
for(int i=0;i<n;i++)
spec[i]=1;
for(k=1;k<n;k++)
{
if(!ds[k].empty())
{
for(auto u:ds[k])
spec[u]=0;
for(int i=0;i<n;i++)
sum[i].clear(),edge[i].clear();
them=tong=0;
for(int i=0;i<n-1;i++)
{
int u=UUU[i],v=VVV[i],w=WWW[i];
tong+=1ll*w;
if((int)g[u].size()<(int)g[v].size())
swap(u,v);
if(spec[u]&&spec[v])
{
edge[u].pb({w,v});
edge[v].pb({w,u});
continue;
}
if(spec[u])
{
sum[u].pb(w);
continue;
}
them+=1ll*w;
}
for(int i=0;i<n;i++)
{
sort(sum[i].begin(),sum[i].end(),greater<ll>());
for(int j=1;j<sum[i].size();j++)
sum[i][j]+=sum[i][j-1];
}
lis.clear();
for(int i=0;i<n;i++)
if(spec[i]==1)
lis.pb(i);
memset(cost,0x3f3f,sizeof(cost));
}
ll res=0;
for(auto u:lis)
if(ktr[u]!=k)
DFS(u,-1),res+=dp[u][1];
kq.pb(res);
}
return kq;
}
#ifdef SKY
int main()
{
freopen("A.inp","r",stdin);
freopen("A.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
vector<int>U(n-1),V(n-1),W(n-1);
for(int i=0;i<n-1;i++)
cin>>U[i]>>V[i]>>W[i];
vector<ll>kq=minimum_closure_costs(n,U,V,W);
for(auto u:kq)cout<<u<<" ";
return 0;
}
#endif
Compilation message (stderr)
roads.cpp: In member function 'long long int nho::solve(int, int, int, const std::vector<long long int>&)':
roads.cpp:48:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
48 | if(v.sc!=p)
| ^
roads.cpp: In function 'long long int get(int, int)':
roads.cpp:80:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | if(sl>=sum[u].size())
| ~~^~~~~~~~~~~~~~~
roads.cpp: In function 'long long int solve(int, int, int, const std::vector<long long int>&)':
roads.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i=0;i<s.size();i++)
| ~^~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:186:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
186 | for(int j=1;j<sum[i].size();j++)
| ~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |