#include "race.h"
#include<bits/stdc++.h>
using namespace std;
int n, k, ans = INT_MAX, proc[200005], si[200005];
vector<pair<int, int>> adj[200005];
map<int, int> occ[2];
void dfs(int i, int p) {
si[i] = 1;
for (auto [j, _] : adj[i]) {
if (proc[j] || j == p) {
continue;
}
dfs(j, i);
si[i] += si[j];
}
}
int centroid(int i, int p, int s) {
for (auto [j, w] : adj[i]) {
if (proc[j] || j == p) {
continue;
}
if (si[j] > s/2) {
return centroid(j, i, s);
}
}
return i;
}
void calc(int i, int p, int d, int path) {
if (path > k) {
return;
}
if (occ[1].find(path) == occ[1].end()) {
occ[1][path] = d;
} else {
occ[1][path] = min(occ[1][path], d);
}
if (k == path) {
ans = min(ans, d);
} else if (occ[0].find(k-path) != occ[0].end()) {
ans = min(ans, d+occ[0][k-path]);
}
for (auto [j, w] : adj[i]) {
if (proc[j] || j == p) {
continue;
}
calc(j, i, d+1, path+w);
}
}
void decompose(int i) {
dfs(i, -1);
if (si[i] == 1) {
return;
}
i = centroid(i, -1, si[i]);
proc[i] = 1;
for (auto [j, w] : adj[i]) {
if (proc[j]) {
continue;
}
calc(j, i, 1, w);
if (occ[0].size() < occ[1].size()) {
occ[0].swap(occ[1]);
}
for (auto c : occ[1]) {
if (occ[0].find(c.first) != occ[0].end()) {
occ[0][c.first] = min(occ[0][c.first], c.second);
} else {
occ[0][c.first] = c.second;
}
}
occ[1].clear();
}
occ[0].clear();
for (auto [j, w] : adj[i]) {
if (proc[j]) {
continue;
}
decompose(j);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for (int i = 0; i < n-1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
decompose(1);
if (ans == INT_MAX) {
return -1;
} else {
return ans;
}
}
