#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> ii;
const int INF = 1e9;
int ans, k;
vector<int> sz, dis, dep;
vector<bool> vis;
vector<vector<ii>> adj;
map<int,int> len, tmp;
void dfs(int cur, int par) {
sz[cur] = 1;
for (auto nx : adj[cur]) {
if (nx.fi == par || vis[nx.fi]) continue;
dfs(nx.fi,cur);
sz[cur] += sz[nx.fi];
}
}
int centroid(int cur, int par, int sub) {
for (auto nx : adj[cur]) {
if (nx.fi == par || vis[nx.fi]) continue;
if (sz[nx.fi]*2 > sub) return centroid(nx.fi,cur,sub);
}
return cur;
}
void getLength(int cur, int par) {
if (!tmp.count(dis[cur])) tmp[dis[cur]] = dep[cur];
else tmp[dis[cur]] = min(tmp[dis[cur]],dep[cur]);
for (auto nx : adj[cur]) {
if (nx.fi == par || vis[nx.fi]) continue;
dis[nx.fi] = dis[cur]+nx.se;
dep[nx.fi] = dep[cur]+1;
getLength(nx.fi,cur);
}
}
void solve(int cur) {
len.clear();
len[0] = dis[cur] = dep[cur] = 0;
for (auto nx : adj[cur]) {
if (vis[nx.fi]) continue;
tmp.clear();
dis[nx.fi] = nx.se;
dep[nx.fi] = 1;
getLength(nx.fi,cur);
// cout << nx.fi << " -> ";
for (auto i : tmp) {
// cout << i.fi << ' ';
if (len.count(k-i.fi)) ans = min(ans,i.se+len[k-i.fi]);
}
// cout << '\n';
for (auto i : tmp) {
if (!len.count(i.fi)) len[i.fi] = i.se;
else len[i.fi] = min(len[i.fi],i.se);
}
}
}
void DnC(int cur) {
dfs(cur,-1);
cur = centroid(cur,-1,sz[cur]);
// cout << cur << " --------------\n";
vis[cur] = 1;
solve(cur);
for (auto nx : adj[cur]) {
if (vis[nx.fi]) continue;
DnC(nx.fi);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
adj = vector<vector<ii>>(N);
for (int i = 0; i < N-1; i++) {
adj[H[i][0]].push_back(ii(H[i][1],L[i]));
adj[H[i][1]].push_back(ii(H[i][0],L[i]));
}
k = K, ans = INF;
vis = vector<bool>(N,0);
sz = dis = dep = vector<int>(N);
DnC(1);
if (ans == INF) return -1;
return ans;
}
