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