#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
const int oo = 1e18;
const int N = 2e5 + 5;
int n, k, mix, ans;
int d = 0;
vector<pair<int,int>> a[N];
struct Centroid{
int sz[N];
int high[N], len[N];
bool cen[N];
map<int, pair<int,int>> mp;
void DFS(int u, int par){
sz[u] = 1;
for(auto e : a[u]){
int v = e.first;
if(v == par || cen[v]){
continue;
}
DFS(v, u);
sz[u] += sz[v];
}
}
int find_centroid(int u, int par, int mx){
for(auto e : a[u]){
int v = e.first;
if(v == par || cen[v]){
continue;
}
if(sz[v] > mx / 2){
return find_centroid(v, u, mx);
}
}
return u;
}
void DFS_ANS(int u, int par, bool check){
if(high[u] > k){
return;
}
if(check){
if(mp[k - high[u]].second != 0){
if(mix > mp[k - high[u]].first + len[u]){
mix = mp[k - high[u]].first + len[u];
}
}
}
else{
auto &x = mp[high[u]];
if(x.first > len[u] || x.second == 0){
x.first = len[u];
x.second = 1;
}
else if(x.first == len[u]){
x.second++;
}
}
for(auto e : a[u]){
int v = e.first, w= e.second;
if(v == par || cen[v]){
continue;
}
len[v] = len[u] + 1;
high[v] = high[u] + w;
DFS_ANS(v, u, check);
}
}
void tree(int u){
mp.clear();
DFS(u, -1);
int centroid = find_centroid(u, -1, sz[u]);
cen[centroid] = true;
mp[0].second = 1;
high[centroid] = len[centroid] = 0;
for(auto e : a[centroid]){
int v = e.first, w = e.second;
if(cen[v]) continue;
high[v] = w;
len[v] = 1;
DFS_ANS(v, centroid, 1);
DFS_ANS(v, centroid, 0);
}
for(auto e : a[centroid]){
int v = e.first;
if(!cen[v]) tree(v);
}
}
};
Centroid Cen;
int best_path(int N, int K, int H[][2], int L[]){
// reset
for(int i = 0; i <= N; i++){
a[i].clear();
Cen.sz[i] = Cen.high[i] = Cen.len[i] = 0;
Cen.cen[i] = false;
}
n = N; k = K;
mix = oo;
ans = 0;
// build graph (OJ.uz cho input 0-indexed)
for(int i=0;i<N-1;i++){
int u = H[i][0];
int v = H[i][1];
int c = L[i];
a[u].push_back({v, c});
a[v].push_back({u, c});
}
Cen.tree(0);
if(ans == 0) return -1;
return 2 * ans;
}
