#include<bits/stdc++.h>
#include "race.h"
using namespace std;
int n, k;
const int MAXN=2e5;
vector<int>tree[MAXN+10];
vector<pair<int, int>>tree1[MAXN+10];
int sz[MAXN+10];
bool marked[MAXN+10];
int ans=1e9;
void dfs(int x, int p)
{
sz[x]=1;
for (auto next:tree[x])
{
if (p==next) continue;
if (marked[next]) continue;
dfs(next, x);
sz[x]+=sz[next];
}
}
int findcentr(int x, int p, int teksz)
{
for (auto next:tree[x])
{
if (p==next) continue;
if (marked[next]) continue;
if (sz[next]>teksz/2) return findcentr(next, x, teksz);
}
return x;
}
vector<pair<int, int>>dists;
void finddist(int root, int p, int x, int d, int len)
{
for (auto next:tree1[x])
{
if (marked[next.first] || next.first==p) continue;
if (d+next.second>k) continue;
if (len>=ans) continue;
dists.push_back({d+next.second, len+1});
finddist(root, x, next.first, d+next.second, len+1);
}
return;
}
unordered_map<int, int>ma;
void decom(int root, int p, int layer)
{
dfs(root, p);
int centr=findcentr(root, p, sz[root]);
//cout<<centr<<" "<<layer<<" dd "<<endl;
marked[centr]=true;
ma={};
for (auto next:tree1[centr])
{
if (!marked[next.first])
{
dists={};
dists.push_back({next.second, 1});
finddist(centr, centr, next.first, next.second, 1);
for (int i=0; i<dists.size(); i++)
{
if (dists[i].first==k)
{
ans=min(ans, dists[i].second);
continue;
}
if (dists[i].first>k)
{
continue;
}
if (dists[i].first<k && ma[k-dists[i].first]!=0)
{
ans=min(ans, ma[k-dists[i].first]+dists[i].second);
}
}
for (int i=0; i<dists.size(); i++)
{
if (dists[i].first<k)
{
if (ma[dists[i].first]!=0) ma[dists[i].first]=min(ma[dists[i].first], dists[i].second);
else ma[dists[i].first]=dists[i].second;
}
}
}
}
for (auto next:tree1[centr])
{
if (!marked[next.first]) decom(next.first, centr, layer+1);
}
return;
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;
k=K;
for (int i=0; i<n-1; i++)
{
tree1[H[i][0]+1].push_back({H[i][1]+1, L[i]});
tree1[H[i][1]+1].push_back({H[i][0]+1, L[i]});
tree[H[i][1]+1].push_back(H[i][0]+1);
tree[H[i][0]+1].push_back(H[i][1]+1);
}
decom(1, 1, 1);
if (ans==1e9) return -1;
return ans;
}
