#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);
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> sub_mn_depth(MAXV, 1e8);
vector<pair<int, int>> dists[MAXV];
vector<int> sub_dists;
void get_dist(int v, int pai, int dist, int depth) {
if (dist > k) return;
sub_mn_depth[dist] = min(sub_mn_depth[dist], depth);
sub_dists.push_back(dist);
for (auto& [viz, w] : adj[v]) {
if (viz == pai or in[viz]) continue;
get_dist(viz, v, dist + w, depth+1);
}
}
int ans = 1e8;
void decomp(int v, int qty) {
dfs(v);
int centroid = find_centroid(v, -1, sz[v]);
in[centroid] = true;
vector<int> all_dists;
// if (centroid == 8) cout << centroid << " é centroid decompondo" << v << endl;
for (auto& [viz, w] : adj[centroid]) {
if (in[viz]) continue;
get_dist(viz, centroid, w, 1);
for (int d : sub_dists) {
dists[d].push_back({sub_mn_depth[d], viz});
sub_mn_depth[d] = 1e8;
all_dists.push_back(d);
}
sub_dists.clear();
}
for (int d : all_dists) {
sort(dists[d].begin(), dists[d].end());
}
if (!dists[k].empty()) ans = min(ans, dists[k][0].first);
for (auto& [viz, w] : adj[centroid]) {
if (in[viz]) continue;
get_dist(viz, centroid, w, 1);
for (int d : sub_dists) {
for (int i=0; d <= k and i<min(2, (int)dists[k-d].size()); i++) {
if (dists[k-d][i].second == viz) continue;
ans = min(ans, dists[k-d][i].first + sub_mn_depth[d]);
}
sub_mn_depth[d] = 1e8;
}
sub_dists.clear();
}
for (int d : all_dists) dists[d].clear();
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});
}
dfs(0);
decomp(0, n);
return (ans == (int)1e8 ? -1 : ans);
}
Compilation message
race.cpp: In function 'void dfs(int, int)':
race.cpp:19:16: error: too few arguments to function 'void dfs(int, int)'
19 | dfs(viz);
| ^
race.cpp:15:6: note: declared here
15 | void dfs(int v, int pai) {
| ^~~
race.cpp: In function 'void decomp(int, int)':
race.cpp:49:10: error: too few arguments to function 'void dfs(int, int)'
49 | dfs(v);
| ^
race.cpp:15:6: note: declared here
15 | void dfs(int v, int pai) {
| ^~~
race.cpp:83:19: error: too few arguments to function 'void decomp(int, int)'
83 | decomp(viz);
| ^
race.cpp:48:6: note: declared here
48 | void decomp(int v, int qty) {
| ^~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:96:10: error: too few arguments to function 'void dfs(int, int)'
96 | dfs(0);
| ^
race.cpp:15:6: note: declared here
15 | void dfs(int v, int pai) {
| ^~~
