#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 = 4e5 + 12;
int rnd(){
return ((rand() << 15) + rand());
}
struct node{
int l = 0, r = 0, pr = 0, tt2 = 0, dval = 0;
ll val = 0, tt1 = 0;
void init(ll _val, int _dval){
l = r = 0, tt1 = tt2 = 0;
val = _val, dval = _dval, pr = rnd();
}
}t[MAXN];
int root, tSize;
void push(int v){
if(!v || !t[v].tt2)
return;
int l = t[v].l, r = t[v].r;
if(l){
t[l].val += t[v].tt1, t[l].tt1 += t[v].tt1;
t[l].dval += t[v].tt2, t[l].tt2 += t[v].tt2;
}
if(r){
t[r].val += t[v].tt1, t[r].tt1 += t[v].tt1;
t[r].dval += t[v].tt2, t[r].tt2 += t[v].tt2;
}
t[v].tt1 = t[v].tt2 = 0;
}
void walk(int v){
if(!v)
return;
push(v);
walk(t[v].l);
cerr << t[v].val << "\n";
walk(t[v].r);
}
void split(int v, int &l, int &r, ll val){
push(v);
if(!v)
return void(l = r = 0);
if(val <= t[v].val)
split(t[v].l, l, t[v].l, val), r = v;
else
split(t[v].r, t[v].r, r, val), l = v;
}
void merge(int &v, int l, int r){
if(!l || !r)
return void(v = l ? l: r);
if(t[l].pr > t[r].pr){
push(l);
merge(t[l].r, t[l].r, r), v = l;
}
else{
push(r);
merge(t[r].l, l, t[r].l), v = r;
}
}
void insert(int &v, int oth){
push(v);
if(!v)
v = oth;
else if(t[v].pr < t[oth].pr){
split(v, t[oth].l, t[oth].r, t[oth].val), v = oth;
}
else{
if(t[oth].val < t[v].val)
insert(t[v].l, oth);
else
insert(t[v].r, oth);
}
}
int isGood(int v, ll val, int dval){
push(v);
if(!v)
return 0;
if(t[v].val == val){
t[v].dval = min(t[v].dval, dval);
return t[v].dval;
}
else if(val < t[v].val)
return isGood(t[v].l, val, dval);
else
return isGood(t[v].r, val, dval);
}
int answer, n, k, sz[MAXN];
vector< pair<int, int> > graph[MAXN];
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;
int tmp = isGood(root, k - cost, n + 12);
if(tmp)
answer = min(answer, tmp + 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;
if(!isGood(root, cost, dist)){
t[++tSize].init(cost, dist);
insert(root, tSize);
}
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);
if(root)
t[root].val += cost, t[root].dval += 1, t[root].tt1 += cost, t[root].tt2 += 1;
int tmp = isGood(root, k, n + 12);
if(tmp)
answer = min(answer, tmp);
}
t[++tSize].init(0, 1);
insert(root, tSize);
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)
root = 0, tSize = 0;
}
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;
}
