#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
const int max_n = 200000;
vector<pair<int,int>> g[max_n];
bool done[max_n];
int sz[max_n], par[max_n];
struct node
{
int dist, len, subtree;
};
bool operator<(const node &a, const node &b)
{
if (a.dist < b.dist)
return true;
else if (a.dist == b.dist)
return make_pair(a.len, a.subtree) < make_pair(b.len, b.subtree);
else
return false;
}
vector<node> nodes;
int k, ans = INT_MAX;
void dfs(int u, int p, int dist, int len, int subtree)
{
if (dist > k || len > ans)
return;
for (auto [v, l] : g[u])
if (v != p && !done[v])
dfs(v, u, dist + l, len + 1, subtree);
nodes.push_back({dist, len, subtree});
}
int find_centroid(int u, int n, int p = -1)
{
for (auto [v, l] : g[u])
if (v != p && !done[v] && sz[v] > n / 2)
return find_centroid(v, n, u);
return u;
}
int find_size(int u, int p = -1)
{
if (done[u]) return 0;
sz[u] = 1;
for (auto [v, l] : g[u])
if (v != p)
sz[u] += find_size(v, u);
return sz[u];
}
void centroid_decomposition(int u = 0, int p = -1)
{
find_size(u);
int c = find_centroid(u, sz[u]);
par[c] = p;
nodes.resize(0);
int subtree = 0;
for (auto [v, l] : g[c])
{
if (!done[v])
dfs(v, c, l, 1, subtree);
nodes.push_back({0, 0, subtree});
subtree++;
}
sort(nodes.begin(), nodes.end());
int lo = 0, hi = nodes.size() - 1;
while (lo < hi)
if (nodes[lo].dist + nodes[hi].dist > k)
hi--;
else if (nodes[lo].dist + nodes[hi].dist < k)
lo++;
else if (nodes[lo].subtree != nodes[hi].subtree)
ans = min(ans, nodes[lo].len + nodes[hi].len), hi--;
else if (nodes[hi].dist == nodes[hi-1].dist)
hi--;
else
lo++;
done[c] = true;
for (auto [v, l] : g[c])
if (!done[v])
centroid_decomposition(v, c);
}
int best_path(int N, int K, int H[][2], int L[])
{
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]});
}
k = K;
centroid_decomposition();
return (ans == INT_MAX ? -1 : ans);
}
