#include "race.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int> > > adjlist;
//weight, node
vector<pair<int,int> > distdepth;
vector<int> subtreesize;
vector<set<pair<int,int> > > paths;
//contains distance, depth
vector<int> use;
int currentMin;
int k;
int distances(int start, int parent){
int sumtrees = 0;
for (auto p : adjlist[start]){
if (p.second==parent){
continue;
}
distdepth[p.second]=make_pair(distdepth[start].first+p.first,distdepth[start].second+1);
sumtrees+=distances(p.second,start);
}
return subtreesize[start]=sumtrees+1;
}
void dfs(int start, int parent){
int maxsub = -1;
int maxind = -1;
for (auto p : adjlist[start]){
if (p.second==parent){
continue;
}
dfs(p.second,start);
if (maxsub<subtreesize[p.second]){
maxind=p.second;
maxsub=subtreesize[p.second];
}
}
//cout<<start<<"===="<<parent<<endl;
auto st = distdepth[start];
//cout<<st.first<<" "<<st.second<<endl;
if (maxind==-1){
paths[use[start]].insert(distdepth[start]);
return;
}
use[start]=use[maxind];
//cout<<"added "<<distdepth[start].first<<" "<<distdepth[start].second<<" to "<<use[start]<<endl;
//cout<<"using "<<use[start]<<endl;
for (auto p : adjlist[start]){
if (p.second==maxind){
continue;
}
for (auto s : paths[use[p.second]]){
//cout<<"insert "<<s.first<<" "<<s.second<<endl;
//check if it matches something in paths[use[maxind]]
auto it = paths[use[start]].lower_bound(make_pair(k+st.first*2-s.first,0));
if (it!=paths[use[start]].end()&&(*it).first==k+st.first*2-s.first){
currentMin=min(currentMin,s.second+(*it).second-2*st.second);
}
}
for (auto s : paths[use[p.second]]){
//add to set
paths[use[start]].insert(s);
}
}
auto it = paths[use[start]].lower_bound(make_pair(k+st.first,0));
if (it!=paths[use[start]].end()&&(*it).first==k+st.first){
currentMin=min(currentMin,(*it).second-st.second);
}
paths[use[start]].insert(distdepth[start]);
}
int best_path(int N, int K, int H[][2], int L[]) {
k=K;
adjlist.resize(N);
for (int i = 0; i<N-1; i++){
adjlist[H[i][0]].push_back(make_pair(L[i],H[i][1]));
adjlist[H[i][1]].push_back(make_pair(L[i],H[i][0]));
}
distdepth.resize(N,make_pair(-1,-1));
subtreesize.resize(N,-1);
distdepth[0]=make_pair(0,0);
distances(0,-1);
paths.resize(N);
use.resize(N);
for (int i = 0; i<N; i++){
use[i]=i;
}
currentMin=N;
dfs(0,-1);
if (currentMin==N){
return -1;
} else {
return currentMin;
}
}
