#include "race.h"
#include<vector>
#include<map>
#include<utility>
#include<iostream>
using namespace std;
vector <pair<int,int> > adj[200005];
map <int,pair<pair<int,int>, pair<int,int> > > M;
bool del[200005];
int Size[200005],SubtreeSize, Centroid, out=42069666,K;
int genSize(int u, int prev) {
if (del[u]) {return(0);}
Size[u]=1; //size
for (auto v: adj[u]) {
if (v.first != prev) {Size[u]+=genSize(v.first,u);}
}
return(Size[u]);
}
void genDists(int u, int depth, int e, int prev, int branch) { //generate distances from root
//printf("derp");
if (depth>(1<<20) or del[u]) {return;}
if (M.find(depth) == M.end()) {
M[depth].first.first=branch; //{branch, e}
M[depth].first.second=e;
M[depth].second.first=-1;
M[depth].second.second=1<<30;
} else {
if (M[depth].first.second>=e) {
M[depth].second.second=M[depth].first.second;
M[depth].second.first=M[depth].first.first;
M[depth].first.second=e;
M[depth].first.first=branch;
} else if (M[depth].second.second>=e) {
M[depth].second.second=e;
M[depth].second.first=branch;
}
}
//printf("%d %d\n",depth,M[depth]);
for (auto v: adj[u]) {
if (v.first != prev) {genDists(v.first,depth+v.second,e+1,u, e ? branch: v.first);} //e is number of edges used
}
}
void FindCentroid(int u, int prev) {
if (del[u] or Centroid or SubtreeSize<=1) {return;}
bool good=true; //break if node done, centroid found, subtree bad
for (auto v: adj[u]) {
if ((!del[v.first]) and v.first != prev and 2*Size[v.first]>SubtreeSize) {
//printf("%d %d %d\n",u,v.first,Size[v.first]);
good=false;
break;
}
}
if (Size[u]*2<SubtreeSize) {good=false;}
if (good) {
genDists(u,0,0,0,0);
for (auto val: M) {
if (M.find(K-val.first) != M.end()) {
if (M[K-val.first].first.first != val.second.first.first) {
out=min(out,val.second.first.second+M[K-val.first].first.second);
//printf("%d %d\n",val.first,val.second.first.second+M[K-val.first].first.second);
}
if (M[K-val.first].second.first != val.second.first.first) {
out=min(out,val.second.first.second+M[K-val.first].second.second);
//printf("%d %d\n",val.first,val.second.first.second+M[K-val.first].first.second);
}
}
}
Centroid=u;
del[u]=true;
} else {
for (auto v: adj[u]) {
if (v.first != prev) {FindCentroid(v.first,u);}
}
}
}
void calcAnswer(int u) {
if (del[u]) {return;}
SubtreeSize=genSize(u,0);
FindCentroid(u,0);
//printf("CENTROID IS %d. Subtree Size is %d\n",Centroid,SubtreeSize);
int temp=Centroid;
Centroid=0;
M.clear();
for (auto v: adj[temp]) {
calcAnswer(v.first);
}
}
int best_path(int n, int k, int H[][2], int L[]) {
K=k;
for (int i=0; i<n-1; i++) {
adj[H[i][0]+1].push_back({H[i][1]+1,L[i]});
adj[H[i][1]+1].push_back({H[i][0]+1,L[i]});
} //1 indexify
calcAnswer(1);
return(out<=n ? out : -1);
}
