#include "race.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define ll long long
#define MP make_pair
using namespace std;
const int MAXN = 2e5 + 12;
int answer, n, k, sz[MAXN];
vector< pair<int, int> > graph[MAXN];
set< pair<ll, int> > stAct, tmpAct;
void dfs_sz(int v, int pr){
sz[v] = 1;
for(pair<int, int> to: graph[v]){
if(to.X != pr){
dfs_sz(to.X, v);
sz[v] += sz[to.X];
}
}
}
void dfs_prep(int v, int pr, ll cost, int dist){
if(cost > k)
return;
auto it = stAct.lower_bound(MP(k - cost, n + 1));
if(prev(it)->X + cost == k){
answer = min(answer, prev(it)->Y + dist);
}
for(pair<int, int> to: graph[v]){
if(to.X == pr)
continue;
dfs_prep(to.X, v, cost + to.Y, dist + 1);
}
}
void dfs_add(int v, int pr, ll cost, int dist){
if(cost > k)
return;
auto it = stAct.lower_bound(MP(cost, 0));
if(it != stAct.end() && it->X == cost && it->Y > dist)
stAct.erase(it), stAct.insert(MP(cost, dist));
else if(it == stAct.end() || it->X != cost)
stAct.insert(MP(cost, dist));
for(pair<int, int> to: graph[v]){
if(to.X == pr)
continue;
dfs_add(to.X, v, cost + to.Y, dist + 1);
}
}
void dfs(int v, int pr, bool keep){
int mx = 0, cost = 0;
for(pair<int, int> to: graph[v]){
if(to.X != pr && sz[mx] < sz[to.X])
mx = to.X, cost = to.Y;
}
for(pair<int, int> to: graph[v]){
if(to.X != pr && mx != to.X)
dfs(to.X, v, 0);
}
if(mx){
dfs(mx, v, 1);
while(!stAct.empty()){
auto cur = *stAct.begin();
stAct.erase(stAct.begin());
cur.X += cost, cur.Y += 1;
if(cur.X > k)
continue;
else if(cur.X == k)
answer = min(answer, cur.Y);
else
tmpAct.insert(cur);
} stAct.swap(tmpAct), tmpAct.clear();
}
stAct.insert(MP(0, 1));
for(pair<int, int> to: graph[v]){
if(to.X != pr && mx != to.X)
dfs_prep(to.X, v, to.Y, 1), dfs_add(to.X, v, to.Y, 2);
}
if(!keep)
stAct.clear();
}
int best_path(int N, int K, int H[][2], int L[]) {
answer = N + 1, n = N, k = K;
for(int i = 0;i < n;i++){
graph[H[i][0] + 1].push_back(MP(H[i][1] + 1, L[i]));
graph[H[i][1] + 1].push_back(MP(H[i][0] + 1, L[i]));
}
dfs_sz(1, 1);
dfs(1, 1, 0);
if(answer == N + 1)
answer = -1;
else
answer -= 1;
return answer;
}
