#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int maxiN = 200000;
#define edge pair<int,int>
#define fils first
#define weight second
vector<edge> links[maxiN];
vector<bool> blocked;
int nbNode;
int target;
int ANS = maxiN*2;
vector<pair<int,int>> solve(int node,int W=0){
//1 - trouver la centroid
map<int,int> sub_tree;
vector<int> nodes;
map<int,vector<int>> subsub;
std::function<int(int, int)> dfs = [&](int node_,int papa=-1){
if(blocked[node_])return 0;
nodes.push_back(node_);
for(auto e:links[node_])if(papa!=e.fils){
int re = dfs(e.fils,node_);
subsub[node_].push_back(re);
sub_tree[node_]+=re;
}
sub_tree[node_]++;
return sub_tree[node_];
};
dfs(node,-1);
int miniDiff = maxiN+42;
int centroid = nodes[0];
for(int nc:nodes){
bool ok;
int maxiDist=0;
int sizeC = nodes.size();
int maxSub = sizeC/2;
for(int d:subsub[nc]){
maxiDist=max(maxiDist,(d<maxSub?0:abs(maxSub-d)));
}
if(nc!=node){
int rest = sizeC-sub_tree[nc];
maxiDist=max(maxiDist,(rest<maxSub?0:abs(maxSub-rest)));
}
if(miniDiff>maxiDist){
miniDiff=maxiDist;
centroid=nc;
}
}
blocked[centroid]=true;
//2 Divide
map<int,int> val;
vector<int> mid;
for(auto e:links[centroid])if(!blocked[e.first]){
vector<pair<int,int>> re = solve(e.fils,e.weight);
for(auto r:re){
if(r.first == target/2 && target%2==0)mid.push_back(r.second);
//On stock le meilleur repréentant pour chaque valeur
if(val.count(r.first)){
val[r.first] = min(val[r.first],r.second);
}else{
val[r.first] = r.second;
}
}
}
//3 Conquer
// On regarde si on a pas trouvé un chemin
sort(mid.begin(),mid.end());
if(mid.size()>1){
ANS = min(ANS,mid[0]+mid[1]);
}
//On en profite pour remplir le vecteur de fin
vector<pair<int,int>> returnPairs;
for(auto key:val){
returnPairs.push_back({key.first+W,key.second+1});
if(key.first==target){
ANS = min(ANS,key.second);
}else if(val.count(target-key.first)){
ANS = min(ANS,(int)(key.second+val[target-key.first]));
}
}
//On oublit pas la ptit nouvelle
returnPairs.push_back({W,1});
return returnPairs;
}
int best_path(int N, int K, int H[][2], int L[])
{
target=K;
nbNode=N;
blocked.resize(N,false);
fill(blocked.begin(),blocked.end(),false);
for(int i = 0;i<N-1;i++){
links[H[i][0]].push_back({H[i][1],L[i]});
links[H[i][1]].push_back({H[i][0],L[i]});
}
solve(0);
return (ANS==2*maxiN?-1:ANS);
}
