#include "race.h"
#include <bits/stdc++.h>
bool dead[200010];
int size[200010];
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){
int sum=0;
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){
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);
}
}
void decompose(int curr){
int total=find_size(curr,-1);
int cen=find_centroid(curr,-1,total);
find_dist(cen,-1,cen,0,0);
dead[cen]=true;
for(auto [to,weight]:adj[cen]){
if(dead[to])continue;
decompose(to);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
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);
int min = 1e9;
for(int i=0;i<N;i++){
std::sort(cenDist[i].begin(),cenDist[i].end());
for(int j=0;j<cenDist[i].size()-1;j++){
if(cenDist[i][j].first==cenDist[i][j+1].first){
cenDist[i][j+1].second.first=cenDist[i][j].second.first=std::min(cenDist[i][j].second.first,cenDist[i][j+1].second.first);
}
}
int l=0,r=cenDist[i].size()-1;
while(l<r){
int sum = cenDist[i][l].first+cenDist[i][r].first;
if(sum>K){
r--;
}
else if(sum<K){
l++;
}
else{
min=std::min(min,cenDist[i][l].second.first+cenDist[i][r].second.first);
r--,l++;
}
}
}
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
*/
