// #include "race.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
const int MAXN = 2e5;
const int MAXV = 1e6+1;
vector<pair<int, int>> adj[MAXN];
bool vis[MAXN];
int sz[MAXN];
bool in[MAXN];
int n, k;
void dfs(int v, int pai) {
sz[v] = 1;
for (auto& [viz, w] : adj[v]) {
if (viz == pai or in[viz]) continue;
dfs(viz, v);
sz[v] += sz[viz];
}
}
int find_centroid(int v, int pai, int qty) {
// cout << "buscando centroid " << v << endl;
for (auto& [viz, w] : adj[v]) {
if (viz == pai or in[viz]) continue;
if (sz[viz] > qty / 2) find_centroid(viz, v, qty);
}
// cout << "é" << v <<endl;
return v;
}
vector<int> dists(MAXV, 1e8);
// op = 1 => preenche, -1 => apaga, 0 => pega resposta
void dfs_dist(int v, int pai, int dist, int depth, int op) {
if (dist > k) return;
if (op == 0)
ans = min(ans, dists[k-dist] + depth);
else if (op == 1)
dists[dist] = min(dists[dist], depth);
else dists[dist] = 1e8;
for (auto& [viz, w] : adj[v]) {
if (viz == pai or in[viz]) continue;
dfs_dist(viz, v, dist + w, depth+1, int op);
}
}
int ans = 1e8;
void decomp(int v) {
dfs(v, -1);
int centroid = find_centroid(v, -1, sz[v]);
in[centroid] = true;
// if (centroid == 8) cout << centroid << " é centroid decompondo" << v << endl;
for (auto& [viz, w] : adj[centroid]) {
if (in[viz]) continue;
dfs_dist(viz, centroid, w, 1, 0); // resposta considera prefixo subárvores
dfs_dist(viz, centroid, w, 1, 1);
}
ans = min(ans, dists[k]);
for (auto& [viz, w] : adj[centroid]) {
if (in[viz]) continue;
dfs_dist(viz, centroid, w, 1, -1);
}
for (auto& [viz, w] : adj[centroid]) {
if (in[viz]) continue;
decomp(viz);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N; k = K;
for (int i=0; i<N-1; i++) {
int u = H[i][0], v = H[i][1];
int w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
decomp(0);
return (ans == (int)1e8 ? -1 : ans);
}
Compilation message
race.cpp: In function 'void dfs_dist(int, int, int, int, int)':
race.cpp:39:9: error: 'ans' was not declared in this scope; did you mean 'abs'?
39 | ans = min(ans, dists[k-dist] + depth);
| ^~~
| abs
race.cpp:45:45: error: expected primary-expression before 'int'
45 | dfs_dist(viz, v, dist + w, depth+1, int op);
| ^~~
