#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 10, maxk = 1e6 + 10, inf = 1e9;
vector < pair < ll, ll > > g[maxn];
ll lvl[maxn], depth[maxn], sub[maxn];
unordered_map < ll, ll > mp, vis;
void pre_dfs(ll v, ll par)
{
sub[v] = 1;
for (ll i = 0; i < g[v].size(); i ++)
{
ll u = g[v][i].first;
if (u == par)
continue;
lvl[u] = lvl[v] + 1;
depth[u] = depth[v] + g[v][i].second;
pre_dfs(u, v);
sub[v] += sub[u];
}
}
ll cnt[maxk], ans, k;
void check_dfs(ll v, ll p, ll root)
{
ll len = (k + depth[root]) - depth[v] + depth[root];
///cout << depth[v] << " " << depth[root] << " " << len << endl;
if (vis[len])
{
ans = min(ans, lvl[v] - lvl[root] + mp[len] - lvl[root]);
///cout << lvl[v] << " - " << lvl[root] << " - " << mp[len] << endl;
}
for (ll i = 0; i < g[v].size(); i ++)
{
ll u = g[v][i].first;
if (u == p)
continue;
check_dfs(u, v, root);
}
}
vector < ll > path;
void add_dfs(ll v, ll p, ll root)
{
ll len = depth[v];
if (vis[len])
mp[len] = min(mp[len], lvl[v]);
else
{
vis[len] = 1;
mp[len] = lvl[v];
}
for (ll i = 0; i < g[v].size(); i ++)
{
ll u = g[v][i].first;
if (u == p)
continue;
add_dfs(u, v, root);
}
}
void dfs(ll v, ll p, bool big, ll last_depth)
{
ll mx = -1, new_depth = 0;
for (ll i = 0; i < g[v].size(); i ++)
{
ll u = g[v][i].first;
if (u == p)
continue;
if (mx == -1 || sub[u] > sub[mx])
mx = u, new_depth = depth[u] - depth[v];
}
for (ll i = 0; i < g[v].size(); i ++)
{
ll u = g[v][i].first;
if (u == p || u == mx)
continue;
dfs(u, v, false, 0);
}
if (mx != -1)
{
dfs(mx, v, true, new_depth);
}
vis[depth[v]] = 1;
mp[depth[v]] = lvl[v];
if (vis[depth[v] + k])
ans = min(ans, mp[depth[v] + k] - lvl[v]);
for (ll i = 0; i < g[v].size(); i ++)
{
ll u = g[v][i].first;
if (u == p || u == mx)
continue;
check_dfs(u, v, v);
add_dfs(u, v, v);
}
/**cout << v << endl;
for (ll i = 0; i <= k; i ++)
cout << cnt[i] << " ";
cout << endl;*/
if (!big)
{
vis.clear();
mp.clear();
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for (ll 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]});
}
pre_dfs(0, -1);
for (ll i = 0; i <= K; i ++)
cnt[i] = inf;
ans = inf;
dfs(0, -1, 1, 0);
if (ans == inf)
return -1;
return ans;
}
