#include "race.h"
#include <bits/stdc++.h>
bool dead[200010];
int size[200010];
int dist[200010];
int length[200010];
int min = 1e9;
int Kg;
std::vector<std::vector<std::pair<int,std::pair<int,int>>>> cenDist;
std::vector<std::vector<std::pair<int,int>>> adj;
int find_size(int curr,int par){
//std::cout << "P" << curr;
int sum=1;
for(auto [to,weight]:adj[curr]){
if(dead[to]||to==par)continue;
sum+=find_size(to,curr);
}
size[curr]=sum;
return sum;
}
int find_centroid(int curr,int par,int total){
for(auto [to,weight]:adj[curr]){
if(dead[to]||to==par)continue;
if(size[to]>total/2){
return find_centroid(to,curr,total);
}
}
return curr;
}
void find_dist(int curr,int par,int cen,int dist,int length,int id){
cenDist[cen].push_back({dist,{length,curr}});
for(auto [to,weight]:adj[curr]){
if(dead[to]||to==par)continue;
find_dist(to,curr,cen,dist+weight,length+1,id);
}
}
void calculate_dist(int curr,int par,std::vector<std::pair<int,int>>& v,std::map<int,int> mp){
if(mp.find(Kg-dist[curr])!=mp.end())min=std::min(min,mp[Kg-dist[curr]]+length[curr]);
v.push_back({dist[curr],length[curr]});
for(auto [to,weight]:adj[curr]){
if(dead[to]||to==par)continue;
dist[to]=dist[curr]+weight;
length[to]=length[curr]+1;
calculate_dist(to,curr,v,mp);
}
}
void decompose(int curr){
int total=find_size(curr,curr);
int cen=find_centroid(curr,curr,total);
//find_dist(cen,-1,cen,0,0);
dead[cen]=true;
length[cen]=0;
dist[cen]=0;
std::map<int,int> mp;
mp[0]=0;
std::vector<std::pair<int,int>> v;
int num=0;
//std::cout << total << ' ' << cen << '\n';
for(auto [to,weight]:adj[cen]){
num++;
if(dead[to])continue;
dist[to]=dist[cen]+weight,length[to]=length[cen]+1;
calculate_dist(to,cen,v,mp);
for(auto [d,l]:v){
if(mp.find(d)!=mp.end())
mp[d]=std::min(mp[d],l);
else
mp[d]=l;
}
v.clear();
//for(auto [d,l]:mp)std::cout << num << ' ' << d << ' ' << l << '\n';
}
for(auto [to,weight]:adj[cen]){
if(dead[to])continue;
decompose(to);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
Kg=K;
adj.resize(N+5);
cenDist.resize(N+5);
for(int i=0;i<N;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);
if(min>=1e9)min=-1;
return min;
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
*/
