#include <bits/stdc++.h>
#define int long long
using namespace std;
struct C_HASH {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM =
chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef long long ll;
const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1000000007;
#define SIZE(a) (int)(a).size()
#define endl '\n'
#define all(x) x.begin(), x.end()
#define ALL(x) begin(x), end(x)
#ifdef LOCAL_PROJECT
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W);
signed main() {
int N;
assert(1 == scanf("%lld", &N));
std::vector<int> U(N - 1), V(N - 1), W(N - 1);
for (int i = 0; i < N - 1; ++i) {
assert(3 == scanf("%lld %lld %lld", &U[i], &V[i], &W[i]));
}
std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) {
if (i > 0) {
printf(" ");
}
printf("%lld", closure_costs[i]);
}
printf("\n");
return 0;
}
#else
#include "roads.h"
#define cerr \
if (false) cerr
#endif
vector<ii> adj[100005];
int dp[100005][2];
int k;
void dfs(int u, int p) {
for (auto &[v, w] : adj[u]) {
if (v == p) {
continue;
}
dfs(v, u);
}
int e = SIZE(adj[u]);
int remove = max(0ll, e - k);
if (remove == 0) {
dp[u][0] = 0;
dp[u][1] = 0;
return;
}
vector<vector<int> > dp2(e + 1, vector<int>(remove + 1, INFL));
dp2[0][0] = 0;
for (int j = 0; j <= remove; ++j) {
for (int i = 1; i <= e; ++i) {
if (adj[u][i - 1].first == p) { // skip over parent
dp2[i][j] = dp2[i - 1][j];
continue;
}
dp2[i][j] = min(dp2[i - 1][j] + dp[adj[u][i - 1].first][1],
dp2[i - 1][j - 1] + dp[adj[u][i - 1].first][0] +
adj[u][i - 1].second);
}
}
dp[u][1] = dp2[e][remove];
dp[u][0] = dp2[e][remove - 1];
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V, std::vector<int> W) {
for (int i = 0; i < N - 1; ++i) {
U[i]++;
V[i]++;
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
vector<int> res(N);
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= N; ++j) {
dp[j][0] = INFL;
dp[j][1] = INFL;
}
k = i;
dfs(1, 0);
res[i] = dp[1][1];
}
return res;
}
Compilation message
roads.cpp: In function 'void dfs(long long int, long long int)':
roads.cpp:71:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
71 | for (auto &[v, w] : adj[u]) {
| ^
/usr/bin/ld: /tmp/ccpeaOCl.o: in function `main':
grader.cpp:(.text.startup+0x26f): undefined reference to `minimum_closure_costs(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
