#include "race.h"
#include <bits/stdc++.h>
#define ad push_back
#define MP make_pair
#define fr first
#define sc second
using namespace std;
const int N = 1e6 + 20;
const int mod = 1e9 + 7;
int n, k;
vector<pair<int, int> > g[N];
int sz[N], col[N], ans = mod, cl[N];
queue <int> q;
void dfs0(int v, int par)
{
sz[v] = 1;
for(auto p : g[v])
{
if(col[p.fr] || p.fr == par) continue;
dfs0(p.fr, v);
sz[v] += sz[p.fr];
}
}
int dfs1(int v, int par, int s)
{
for(auto p : g[v])
{
if(col[p.fr] || p.fr == par) continue;
if(sz[p.fr] > s / 2) return dfs1(p.fr, v, s);
}
return v;
}
void dfs(int v, int par, int l, int d, int bl)
{
if(bl == 0)
{
cl[d] = mod;
if(d <= k) cl[k - d] = mod;
}
if(bl == 1) if(d <= k) ans = min(ans, l + cl[k - d]);
if(bl == 2) cl[d] = min(cl[d], l);
for(auto p : g[v])
{
if(p.fr == par || col[p.fr]) continue;
dfs(p.fr, v, l + 1, min(k + 1, d + p.sc), bl);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N; k = K;
for (int i = 0; i < n - 1; i++)
{
g[H[i][0]].ad(MP(H[i][1], L[i]));
g[H[i][1]].ad(MP(H[i][0], L[i]));
}
q.push(1);
while(!q.empty())
{
int c = q.front();
dfs0(c, c);
c = dfs1(c, c, sz[c]);
q.pop();
col[c] = 1;
for(auto p : g[c]) if(!col[p.fr]) q.push(p.fr);
dfs(c, c, 0, 0, 0);
cl[0] = 0;
for(auto p : g[c])
{
if(!col[p.fr])
{
dfs(p.fr, c, 1, p.sc, 1);
dfs(p.fr, c, 1, p.sc, 2);
}
}
}
if(ans == mod) return -1;
return ans;
}
