#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");
typedef long long i64;
const int nmax = 2e5;
static i64 K;
static int ans;
bool viz[nmax + 1];
int lant[nmax + 1], sz[nmax + 1];
i64 ct[nmax + 1];
vector<pair<int, int>> g[nmax + 1];
set<pair<i64, int>> s[nmax + 1];
void dfs (int nod, int h, int dad = -1) {
viz[nod] = 1;
sz[nod] = 1;
int mxf = -1, mxg = -1, valm = 0;
for (auto i : g[nod]) {
if (viz[i.first] == 0) {
dfs(i.first, h + 1, nod);
sz[nod] += sz[i.first];
if (sz[i.first] > mxg) {
mxg = sz[i.first];
mxf = i.first;
valm = i.second;
}
}
}
if (mxf == -1) {
lant[nod] = nod;
} else {
lant[nod] = lant[mxf];
}
ct[lant[nod]] += valm;
set<pair<i64, int>>::iterator it = s[lant[nod]].lower_bound({K - ct[lant[nod]] - 0, 0});
if (it != s[lant[nod]].end() && (it -> first) == K - ct[lant[nod]]) {
ans = min(ans, (it -> second) - h);
}
s[lant[nod]].insert({0, h});
for (auto i : g[nod]) {
if (i.first == mxf || i.first == dad)
continue;
int l = lant[i.first];
ct[l] += i.second;
while (!s[l].empty()) {
pair<i64, int> x = *s[l].begin();
s[l].erase(s[l].begin());
x.first += ct[l];
it = s[lant[nod]].lower_bound({K - ct[lant[nod]] - x.first, 0});
if (it != s[lant[nod]].end() && (it -> first) == K - ct[lant[nod]] - x.first) {
ans = min(ans, x.second + (it -> second) - 2 * h);
}
s[lant[nod]].insert({x.first - ct[lant[nod]], x.second});
}
}
}
int best_path (int n, i64 k, int h[nmax + 1][2], int l[nmax + 1]) {
K = k;
for (int i = 0; i < n - 1; ++ i) {
g[h[i][0]].push_back({h[i][1], l[i]});
g[h[i][1]].push_back({h[i][0], l[i]});
}
ans = n + 1;
dfs(0, 0);
++ ans;
if (ans == n + 2)
ans = -1;
return ans;
}
/*int main() {
int a[2][2]= {{0, 1}, {1, 2}};
int b[2] = {1, 1};
cout << best_path (3, 3, a, b) << "\n";
return 0;
}*/
Compilation message
/tmp/ccHhw2Lc.o: In function `main':
grader.cpp:(.text.startup+0x20): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status
