#include <race.h>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < ll, ll >
#define mk make_pair
#define fr first
#define sc second
#define pb push_back
#define ok puts("ok");
const int N = (int)2e5 + 7;
const int nn = (int)1e6 + 7;
ll can[nn], mnpath[nn];
int n, k, book;
vector < pii > gr[N];
int sz[N];
bool del[N];
ll ans = -1;
void dfs(int v, int pr) {
sz[v] = 1;
for (auto to : gr[v]) {
if (to.fr == pr || del[to.fr]) continue;
dfs(to.fr, v);
sz[v] += sz[to.fr];
}
}
int findcentroid(int v) {
int now = v;
int siz = sz[v];
int pr = -1;
bool fl = 1;
while (1) {
fl = 1;
for (auto to : gr[now]) {
if (to.fr == pr || del[to.fr]) continue;
if (sz[to.fr] * 2 >= siz) {
pr = now;
now = to.fr;
fl = 0;
break;
}
}
if (fl) break;
}
return now;
}
void dfs1(int v, int pr, int curcost, int curlen, int tp) {
if (curcost > k)
return ;
if (tp == 0) {
if (can[k - curcost] == book) {
if (curlen + mnpath[k - curcost] < ans || ans == -1) {
ans = curlen + mnpath[k - curcost];
}
}
if (curcost == k && (curlen < ans || ans == -1)) {
ans = curlen
}
} else {
if (can[curcost] < book) {
can[curcost] = book;
mnpath[curcost] = curlen;
} else if (curlen < mnpath[curcost]) {
can[curcost] = book;
mnpath[curcost] = curlen;
}
}
for (auto to : gr[v]) {
if (to.fr == pr || del[to.fr]) continue;
dfs1(to.fr, v, curcost + to.sc, curlen + 1, tp);
}
}
void compute(int v) {
dfs(v, 0);
if (sz[v] <= 1)
return ;
int centroid = -1;
centroid = findcentroid(v);
book++;
for (auto to : gr[centroid]) {
if (del[to.fr]) continue;
dfs1(to.fr, centroid, to.sc, 1, 0);
dfs1(to.fr, centroid, to.sc, 1, 1);
}
// printf("### %d %d\n", centroid, ans);
del[centroid] = 1;
for (auto to : gr[centroid]) {
if (del[to.fr]) continue;
compute(to.fr);
}
}
int best_path (int _n, int _k, int _h[][2], int _l[]) {
n = _n; k = _k;
for (int i = 0; i < n - 1; i++) {
ll u, v, w;
u = _h[i][0] + 1; v = _h[i][1] + 1; w = _l[i];
gr[v].pb(mk(u, w));
gr[u].pb(mk(v, w));
}
compute(1);
return ans;
}
Compilation message
race.cpp: In function 'void dfs1(int, int, int, int, int)':
race.cpp:65:3: error: expected ';' before '}' token
}
^
