#include <bits/stdc++.h>
#include "race.h"
#define DEBUG 0
using namespace std;
const int N = 2e5 + 10;
const int INF = 1e9 + 7;
vector <pair <int, int>> adj[N];
int sz[N];
bool visited[N];
map <long long, int> mp;
int ans = INF;
int find_size(int u, int p) {
sz[u] = 1;
for(auto [v, w] : adj[u]) {
if(v == p || visited[v]) {
continue;
}
sz[u] += find_size(v, u);
}
return sz[u];
}
int find_centroid(int u, int p, int n) {
for(auto [v, w] : adj[u]) {
if(v == p || visited[v]) {
continue;
}
if(sz[v] > n / 2) {
return find_centroid(v, u, n);
}
}
return u;
}
void dfs(int u, int p, long long total, bool state, int depth, int K) {
if(state) {
if(mp.count(total)) {
mp[total] = min(mp[total], depth);
}
else {
mp[total] = depth;
}
}
else {
if(mp.count(K - total)) {
ans = min(ans, depth + mp[K - total]);
}
}
for(auto [v, w] : adj[u]) {
if(v == p || visited[v]) {
continue;
}
dfs(v, u, total + w, state, depth + 1, K);
}
}
void centroid(int u, int K) {
int c = find_centroid(u, -1, find_size(u, -1));
visited[c] = 1;
mp.clear();
mp.emplace(0, 0);
for(auto [v, w] : adj[c]) {
if(visited[v]) {
continue;
}
dfs(v, -1, w, 0, 1, K);
dfs(v, -1, w, 1, 1, K);
}
for(auto [v, w] : adj[c]) {
if(visited[v]) {
continue;
}
centroid(v, K);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for(int i = 0; i < N - 1; i++) {
H[i][0]++, H[i][1]++;
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
centroid(1, K);
if(ans == INF) {
ans = -1;
}
return ans;
}
