#include "race.h"
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
typedef long long ll;
int k;
set<pair<int,int>> nodes[50000];
int parents[50000];
int sub_size[50000];
int depth[50000];
int abs_depth[50000];
void init_tree(int node,int par,int d=0,int abs_d=1){
//cout<<node+1<<" "<<par+1<<"\n";
parents[node]=par;
depth[node]=d;
abs_depth[node]=abs_d;
sub_size[node]=0;
for(pair<int,int> ne:nodes[node]){
if(ne.first!=par){
init_tree(ne.first,node,d+ne.second,abs_d+1);
sub_size[node]+=sub_size[ne.first];
}
}
sub_size[node]++;
//cout<<"done "<<node+1<<"\n";
}
int get_centroid(int node){
int n=sub_size[node];
int centroid=node;
while(sub_size[centroid]>n/2){
int biggest_size=-1;
int biggest=-1;
for(pair<int,int> ne:nodes[centroid]){
//cout<<ne<<" "<<parents[centroid]<<" "<<sub_size[ne]<<"\n";
if(ne.first!=parents[centroid]&&sub_size[ne.first]>=biggest_size){
biggest_size=sub_size[ne.first];
biggest=ne.first;
}
}
centroid=biggest;
}
return parents[centroid];
}
vector<pair<int,int>> get_depths(int node, int add){
vector<pair<int,int>> depths;
queue<int> q;
q.push(node);
while(!q.empty()){
int c=q.front();
q.pop();
depths.push_back({depth[c]+add,abs_depth[c]});
for(pair<int,int> ne:nodes[c])
if(ne.first!=parents[c])
q.push(ne.first);
}
return depths;
}
int get_pairs2(vector<pair<int,int>>&a,vector<pair<int,int>>&b,int s){
reverse(a.begin(),a.end());
int l=0;
int res=1000000;
for(pair<int,int> i:a){
int rec=s-i.first;
while(l<(int)b.size()&&b[l].first<rec)
l++;
if(l<(int)b.size()&&b[l].first+i.first==s)
res=min(res,b[l].second+i.second);
}
//cout<<"pairs2: "<<res<<"\n";
return res;
}
int get_pairs(vector<vector<pair<int,int>>>vec,int s){
/*cout<<"-------\n";
for(vector<int> i:vec){
for(int j:i)
cout<<j<<" ";
cout<<"\n";
}*/
int n=(int)vec.size();
if(n==1){
auto iter=lower_bound(vec[0].begin(),vec[0].end(),pair<int,int>(s,0));
if(iter==vec[0].end()||iter->first!=s)
return 1000000;
return iter->second;
}
int res=1000000;
int m=n/2;
vector<pair<int,int>>a,b;
for(int i=0;i<n;i++){
if(i<m)
a.insert(a.end(),vec[i].begin(),vec[i].end());
else
b.insert(b.end(),vec[i].begin(),vec[i].end());
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
res=min(res,get_pairs2(a,b,s));
res=min(res,get_pairs({vec.begin(),vec.begin()+m},s));
res=min(res,get_pairs({vec.begin()+m,vec.end()},s));
//cout<<"pairs1: "<<res<<"\n";
return res;
}
int get(int node){
if(nodes[node].empty())
return 1000000;
int centroid=get_centroid(node);
init_tree(centroid,centroid);
vector<pair<int,int>> children(nodes[centroid].begin(),nodes[centroid].end());
vector<vector<pair<int,int>>>vec;
for(pair<int,int> child:children){
nodes[centroid].erase(child);
nodes[child.first].erase({centroid,child.second});
init_tree(child.first,child.first);
vec.push_back(get_depths(child.first,child.second));
}
int res=get_pairs(vec,k);
for(pair<int,int> child:children){
init_tree(child.first,child.first);
res=min(res,get(child.first));
}
return res;
}
int best_path(int N, int K, int H[][2], int L[]) {
int n=N;
k=K;
for(int i=0;i<n-1;i++){
int a=H[i][0],b=H[i][1];
nodes[a].insert({b,L[i]});
nodes[b].insert({a,L[i]});
}
init_tree(0,0);
int res=get(0);
if(res>=1000000)
return -1;
return res;
}
