#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
int n, k, ans = -1;
int sz[maxn], mark[maxn], cnt[maxn];
vector<pair<int,int>> adj[maxn];
void get_size(int x, int p)
{
sz[x] = 1;
for (auto [i, j] : adj[x]) if (i != p && !mark[i])
get_size(i, x),
sz[x] += sz[i];
}
int find(int x, int p, int half)
{
for (auto [i, j] : adj[x]) if (i != p && !mark[i] && sz[i] > half)
return find(i, x, half);
return x;
}
void dfs(int x, int p, int h, int d, int t)
{
if (h > k) return;
if (t == 0)
{
if (cnt[k - h] != -1)
{
if (ans == -1)
ans = d + cnt[k - h];
else ans = min(ans, d + cnt[k - h]);
}
} else if (cnt[h] == -1) cnt[h] = d; else cnt[h] = min(cnt[h], d);
for (auto [i, j] : adj[x]) if (i != p)
dfs(i, x, h + j, d + 1, t);
}
void reset(int x, int p, int h)
{
if (h > k) return;
cnt[h] = -1;
for (auto [i, j] : adj[x])if (i != p && !mark[i])
reset(i, x, h + j);
}
void solve(int x = 1)
{
get_size(x, x);
x = find(x, x, sz[x] / 2);
mark[x] = 1;
cnt[0] = 0;
for (auto [i, j] : adj[x]) if (!mark[i])
dfs(i, x, j, 1, 1),
dfs(i, x, j, 1, 0);
reset(x, x, 0);
for (auto [i, j] : adj[x]) if (!mark[i])
solve(i);
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N, k = K;
memset(cnt, -1, sizeof cnt);
for(int i = 0; i < n - 1; i++){
int u = H[i][0] + 1, v = H[i][1] + 1, w = L[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
solve();
return ans;
}
//signed main()
//{
// ios_base::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
//// freopen("test.inp", "r", stdin);
//// freopen("test.out", "w", stdout);
// cin >> n >> k;
// for(int i = 0; i < n - 1; i++){
// int u, v, w; cin >> u >> v >> w;
// u++; v++;
// adj[u].emplace_back(v, w);
// adj[v].emplace_back(u, w);
// }
// memset(cnt, -1, sizeof cnt);
// solve();
// cout << ans;
//}
Compilation message
/usr/bin/ld: /tmp/ccjjThdA.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status
