//#pragma once
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 3;
int k;
vector<pair<int,int>>adj[N];
bool marked[N];
int sub[N];
int sz;
int ans = 1e9;
int dfs_subtree(int node, int prev){
sub[node] = 1;
for(auto& edge : adj[node]){
if(edge.first != prev && !marked[edge.first]){
sub[node] += dfs_subtree(edge.first, node);
}
}
return sub[node];
}
int find_centroid(int node, int prev){
for(auto& edge : adj[node]){
if(edge.first != prev && !marked[edge.first] && 2 * sub[edge.first] > sz){
return find_centroid(edge.first, node);
}
}
return node;
}
vector<pair<int,int>>weights[N];
vector<pair<int,int>>all;
void dfs(int start, int node, int prev, int cur, int len){
if(cur>k)return;
weights[start].push_back({cur,len});
all.push_back({cur,len});
for(auto & edge : adj[node]){
if(edge.first != prev && !marked[edge.first]){
dfs(start, edge.first, node, cur + edge.second, len + 1);
}
}
}
void decompose(int node){
dfs_subtree(node, -1);
sz = sub[node];
int c = find_centroid(node, -1);
for(auto& edge : adj[c]){
if(marked[edge.first])continue;
dfs(edge.first, edge.first, c, edge.second, 1);
}
for(auto& edge : adj[c]){
if(marked[edge.first])continue;
int child = edge.first;
for(auto& p : weights[child]){
int d = k - p.first;
// child either doesnt have d or has (d, l), (d, l + 1), ..., (d, r)
auto l = lower_bound(weights[child].begin(), weights[child].end(), make_pair(d,0));
if(l == weights[child].end() || l->first != d){//child doesnt have d
auto it = lower_bound(all.begin(),all.end(),make_pair(d,0));
if(it != all.end() && it->first == d){
ans = min(ans, p.second + it->second);
}
}else{
auto r = upper_bound(weights[child].begin(), weights[child].end(), make_pair(d, (int)1e9)) - 1;
auto it = lower_bound(all.begin(), all.end(), make_pair(d,0));
if(it->second >= l->second){
it = upper_bound(all.begin(),all.end(),make_pair(r->first, r->second));
if(it != all.end() && it->first == d){
ans = min(ans, p.second + it->second);
}
}else{
ans = min(ans, p.second + it->second);
}
}
}
}
marked[c] = 1;
all.clear();
all.shrink_to_fit();
for(auto& edge : adj[c]){
int child = edge.first;
if(!marked[child]){
weights[child].clear();
weights[child].shrink_to_fit();
decompose(child);
}
}
}
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]});
}
decompose(0);
return ans;
}
