#include "race.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int>>> g;
vector<int> sz, d, dis;
map<int, multiset<int>> mp;
vector<vector<int>> vec;
int ans=1e9, k;
void dfssz(int no, int rt, int cnt, int di) {
sz[no] = 1;
d[no] = cnt;
dis[no] = di;
for(auto i: g[no]) {
if(i.first == rt) continue;
dfssz(i.first, no, cnt+1, di+i.second);
sz[no] += sz[i.first];
}
}
void dfs(int no, int rt, int kp) {
int mxsz = -1, big = -1;
for(auto i: g[no]) {
if(i.first == rt) continue;
if(sz[i.first] > mxsz) {
mxsz = sz[i.first];
big = i.first;
}
}
for(auto i: g[no]) {
if(i.first == rt || i.first == big) continue;
dfs(i.first, no, 0);
}
if(big != -1) {
dfs(big, no, 1);
swap(vec[no], vec[big]);
}
for(auto i: g[no]) {
if(i.first == rt || i.first == big) continue;
for(auto j: vec[i.first]) {
mp[dis[j]].insert(d[j]);
vec[no].push_back(j);
}
}
if(!mp[k+dis[no]].empty()) {
ans = min(ans, *mp[k+dis[no]].begin()-d[no]);
}
vec[no].push_back(no);
mp[dis[no]].insert(d[no]);
for(auto i: g[no]) {
if(i.first == rt || i.first == big) continue;
for(auto j: vec[i.first]) {
mp[dis[j]].erase(mp[dis[j]].find(d[j]));
}
for(auto j: vec[i.first]) {
int val = k+2*dis[no]-dis[j];
if(!mp[val].empty()) {
ans = min(ans, d[j]+*mp[val].begin()-2*d[no]);
}
}
for(auto j: vec[i.first]) {
mp[dis[j]].insert(d[j]);
}
}
if(kp == 0) {
for(auto i: vec[no]) {
mp[dis[i]].erase(mp[dis[i]].find(d[i]));
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
g.assign(N+2, vector<pair<int, int>>());
vec.assign(N+2, vector<int>());
dis.assign(N+2, 0); d.assign(N+2, 0); sz.assign(N+2, 0);
for(int i=0; i<N-1; i++) {
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
dfssz(0, -1, 0, 0);
dfs(0, -1, 1);
if(ans == 1e9) return -1;
else return ans;
}
