#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <cassert>
#include "race.h"
using namespace std;
#define INF 1145141919
#define rep(i, n) for (int i=0; i<(n); i++)
#define _1 first
#define _2 second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef pair<int, int> P;
inline void chmin(int &x, int v) { if (x > v) x = v; }
int N, K;
int ans;
bool dead[200000];
vector<P> G[200000];
multiset<int> C[1000001];
void merge(vector<vector<P> > vs) {
if (vs.empty()) return;
for (vector<P> &ps : vs) for (P &x : ps) {
if (x._1 == K) chmin(ans, x._2);
}
if (vs.size() < 2) return;
//for (auto &p : vs) { cout<<"{"; for (P &x : p)cout<<"("<<x._1<<","<<x._2<<"),"; cout<<"},"; } cout<<"\n";
for (vector<P> &ps : vs) for (P &x : ps) C[x._1].insert(x._2);
for (vector<P> &ps : vs) {
for (P &x : ps) C[x._1].erase(C[x._1].find(x._2));
for (P &x : ps) {
if (!C[K-x._1].empty()) chmin(ans, x._2 + *C[K-x._1].begin());
}
for (P &x : ps) C[x._1].insert(x._2);
}
for (vector<P> &ps : vs) for (P &x : ps) C[x._1].clear();
}
int sz[200000];
int all;
void dfs2(int x, int p) {
sz[x] = 1;
for (P pp : G[x]) {
int t = pp._1;
if (dead[t] || t == p) continue;
dfs2(t, x);
sz[x] += sz[t];
}
}
P dfs3(int x, int p) {
P mp = P(INF, -1);
int mc = all-sz[x];
for (P pp : G[x]) {
int t = pp._1;
if (dead[t] || t == p) continue;
mp = min(mp, dfs3(t, x));
mc = max(mc, sz[t]);
}
return min(mp, P(mc, x));
}
int centroid(int s) {
dfs2(s, -1);
all = sz[s];
return dfs3(s, -1)._2;
}
void dfs(int x, int p, int d, int r, vector<P> &ret) {
if (d > K) return;
ret.pb(P(d, r));
for (P pp : G[x]) {
int t = pp._1;
if (dead[t] || t == p) continue;
dfs(t, x, d+pp._2, r+1, ret);
}
}
vector<P> solve(int s) {
vector<P> ret;
dfs(s, -1, 0, 0, ret);
int g = centroid(s);
dead[g] = true;
vector<vector<P> > vs;
for (P pp : G[g]) {
int t = pp._1;
if (dead[t]) continue;
vector<P> cs = solve(t);
vector<P> new_cs;
for (P x : cs) if (x._1+pp._2 <= K) new_cs.pb(P(x._1+pp._2, x._2+1));
vs.pb(new_cs);
}
merge(vs);
return ret;
}
int best_path(int n, int k, int H[][2], int L[]) {
N = n, K = k;
rep(i, N) G[i].clear(), dead[i] = false;
rep(i, 1000001) C[i].clear();
rep(i, N-1) {
G[H[i][0]].pb(P(H[i][1], L[i]));
G[H[i][1]].pb(P(H[i][0], L[i]));
}
ans = INF;
int g = centroid(0);
dead[g] = true;
vector<vector<P> > vs;
for (P pp : G[g]) {
int t = pp._1;
if (dead[t]) continue;
vector<P> cs = solve(t);
vector<P> new_cs;
for (P x : cs) if (x._1+pp._2 <= K) new_cs.pb(P(x._1+pp._2, x._2+1));
vs.pb(new_cs);
}
merge(vs);
if (ans == INF) ans = -1;
return ans;
}
