#include "race.h"
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
struct edge{
int neigh;
int weight;
};
const int maxiN = 2e5;
vector<edge> links[maxiN];
bool erased[maxiN];
int sz[maxiN];
void compute_sz(int node, int papa=-1){
sz[node] = 1;
for(auto e:links[node])if(papa != e.neigh && !erased[e.neigh]){
compute_sz(e.neigh,node);
sz[node] += sz[e.neigh];
}
}
int get_centroid(int node, int size_c, int papa=-1){
for(auto &e: links[node])
if(!erased[e.neigh] && sz[e.neigh]*2>size_c && papa != e.neigh)
return get_centroid(e.neigh, size_c,node);
return node;
}
void dfs(int node, int papa, int depth,int weight,vector<pair<int,int>> &dw){
dw.push_back(make_pair(weight, depth));
for(auto &e:links[node])if(e.neigh != papa && !erased[e.neigh])
dfs(e.neigh,node,depth+1,weight+e.weight,dw);
}
int ans = 2*maxiN;
void centroid_decomposition(int node, int k){
compute_sz(node);
int X = get_centroid(node, sz[node]);
unordered_map<int, int> mem;
mem[0]=0;
for(auto e:links[X])if(!erased[e.neigh]){
vector<pair<int,int>> wd;
dfs(e.neigh, X, 1,e.weight, wd);
for(auto &[w,d]:wd)
if(mem.count(k-w))
ans = min(ans, d + mem[k - w]);
for(auto &[w,d]:wd){
if(mem.count(w))
mem[w] = min(mem[w], d);
else
mem[w] = d;
}
}
erased[X] = true;
for(auto &e:links[X])if(!erased[e.neigh])
centroid_decomposition(e.neigh, k);
}
int best_path(int N, int K, int H[][2], int L[])
{
for(int i = 0 ; i < N - 1 ; i++){
links[H[i][1]].push_back({H[i][0], L[i]});
links[H[i][0]].push_back({H[i][1], L[i]});
}
centroid_decomposition(0, K);
return (ans==2*maxiN?-1:ans);
}
