#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef pair<int,int> pii;
vector<pii> adj[200001],nw;
int sz[200001], ans,k;
int H[200001][2], L[200001];
bool centroid[200001];
map<int,int> mindist;
int dist[200001], len[200001];
int dfs (int cur ,int p) {
sz[cur] = 1;
for (pii i : adj[cur]) if(i.first != p && !centroid[i.first]) sz[cur] += dfs(i.first,cur);
return sz[cur];
}
void firstlength (int cur, int par, int down, int length) {
if (mindist.find(down) == mindist.end() || length < mindist[down])
mindist[down] = length;
if (down == k) ans = min(ans,length);
for (pii p : adj[cur]) if (!centroid[p.first] && p.first != par) firstlength(p.first,cur,down+p.second,length+1);
}
void findlength (int cur ,int par ,int down, int length) {
if (down == k) ans = min(ans,length);
if (mindist.find(down) == mindist.end() || mindist[down] > length) nw.push_back({down,length});
if (mindist.find(k-down) != mindist.end()) ans = min(ans,length+mindist[k-down]);
for (pii p : adj[cur]) if (!centroid[p.first] && p.first != par) findlength(p.first,cur,down+p.second,length+1);
}
int findCentroid (int cur, int p, int n) {
for (pii i : adj[cur])
if (i.first != p && !centroid[i.first] && sz[i.first] > (n>>1))
return findCentroid (i.first,cur,n);
return cur;
}
void solve (int cur) {
dfs(cur,-1);
int cent = findCentroid(cur,-1,sz[cur]);
centroid[cent] = 1;
mindist.clear();
int i;
for (i = 0; i < adj[cent].size() ; i++) if (!centroid[adj[cent][i].first]) {firstlength(adj[cent][i].first,cent,adj[cent][i].second,1); break;}
for (i++; i < adj[cent].size(); i++) if (!centroid[adj[cent][i].first]) {
findlength(adj[cent][i].first,cent,adj[cent][i].second,1);
while (!nw.empty()) mindist[nw.back().first] = nw.back().second, nw.pop_back();
}
for (pii p : adj[cent]) if (!centroid[p.first]) solve(p.first);
}
int best_path(int n, int K, int h[][2], int l[]) {
k=K;
for (int i = 0; i < n-1; i++) {
adj[h[i][0]].push_back({h[i][1],l[i]});
adj[h[i][1]].push_back({h[i][0],l[i]});
}
ans = INT_MAX;
solve(0);
return ans == INT_MAX ? -1 : ans;
}
