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