#include "roads.h" #include <vector> #include <iostream> #include <algorithm> using namespace std; const int maxN = 2000; int N; vector<int> edge[maxN]; vector<long long> wt[maxN]; vector<int> P(maxN, -1); vector<long long> P_wt(maxN, 0); void dfs(int u) { for(int e = 0; e < edge[u].size(); e++) { int v = edge[u][e]; long long w = wt[u][e]; if(P[u] == v) continue; P[v] = u; P_wt[v] = w; dfs(v); } } int K; long long dp1[maxN]; long long dp2[maxN]; void dfs2(int u) { // cerr << "\n"; // cerr << "dfs2 " << u << '\n'; dp1[u] = 0; dp2[u] = 0; vector<long long> adj; if(edge[u].size() == 1 && u != 0) { dp1[u] = dp2[u] = 0; return; } for(int v: edge[u]) { if(P[u] == v) continue; dfs2(v); dp1[u] += dp2[v]; dp2[u] += dp2[v]; adj.push_back(P_wt[v] + dp1[v] - dp2[v]); } sort(adj.begin(), adj.end()); // cerr << "u = " << u << '\n'; // cerr << "adj = "; // for(long long a: adj) cerr << a << ' '; // cerr << '\n'; int x1 = max(int(adj.size() - K), 0); // cerr << "dp1 " << u << " = " << dp1[u] << ", dp2 " << u << " = " << dp2[u] << '\n'; for(int i = 0; i < x1; i++) dp1[u] += adj[i]; for(int i = x1; i < adj.size(); i++) dp1[u] += min(0LL, adj[i]); int x2 = max(int(adj.size() - (K-1)), 0); for(int i = 0; i < x2; i++) dp2[u] += adj[i]; for(int i = x2; i < adj.size(); i++) dp2[u] += min(0LL, adj[i]); // cerr << "dp1 " << u << " = " << dp1[u] << ", dp2 " << u << " = " << dp2[u] << '\n'; } vector<long long> minimum_closure_costs(int n1, vector<int> u1, vector<int> v1, vector<int> c1) { long long total_weight = 0; N = n1; for(int j = 0; j < N-1; j++) { edge[ u1[j] ].push_back( v1[j] ); wt[ u1[j] ].push_back( c1[j] ); edge[ v1[j] ].push_back( u1[j] ); wt[ v1[j] ].push_back( c1[j] ); total_weight += c1[j]; } dfs(0); vector<long long> res(N); res[0] = total_weight; for(K = 1; K <= N-1; K++) { // cerr << "\n\n\n\n"; // cerr << "K = " << K << '\n'; dfs2(0); res[K] = min(dp1[0], dp2[0]); } return res; }

roads.cpp: In function 'void dfs(int)':
roads.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int e = 0; e < edge[u].size(); e++)
      |                    ~~^~~~~~~~~~~~~~~~
roads.cpp: In function 'void dfs2(int)':
roads.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = x1; i < adj.size(); i++)
      |                     ~~^~~~~~~~~~~~
roads.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i = x2; i < adj.size(); i++)
      |                     ~~^~~~~~~~~~~~