#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define f first
#define s second
const int mxN = 200000;
const int mxK = 1000000;
int n, k;
vector< pair<int, int> > adj[mxN + 5];
int n_child[mxN + 5];
int cnt[mxK + 5];
bool used[mxN + 5];
vector<int> order;
int mx_depth;
int result;
int get_subtree_size(int u, int p = -1) {
n_child[u] = 1;
for (auto& to: adj[u]) {
if (!used[to.f] && to.f != p) {
n_child[u] += get_subtree_size(to.f, u);
}
}
return n_child[u];
}
int get_centroid(int desired, int u, int p = -1) {
for (auto& to: adj[u]) {
if (!used[to.f] && to.f != p && n_child[to.f] >= desired) {
return get_centroid(desired, to.f, u);
}
}
return u;
}
void get_cnt(int u, int p, bool e, int w, int depth) {
if (w > k) {
return ;
}
order.push_back(w);
if (e) {
cnt[w] = min(cnt[w], depth);
}
else {
result = min(result, cnt[k - w] + depth);
}
for (auto& to: adj[u]) {
if (!used[to.f] && to.f != p) {
get_cnt(to.f, u, e, w + to.s, depth + 1);
}
}
}
void centroid_decomp(int u) {
int centroid = get_centroid(get_subtree_size(u) >> 1, u);
used[centroid] = true;
mx_depth = 0;
for (auto& to: adj[centroid]) {
if (!used[to.f]) {
get_cnt(to.f, centroid, false, to.s, 1);
get_cnt(to.f, centroid, true, to.s, 1);
}
}
for (auto& v: order) {
cnt[v] = n + 5;
}
order.clear();
for (auto& to: adj[centroid]) {
if (!used[to.f]) {
centroid_decomp(to.f);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N, k = K;
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]);
}
cnt[0] = 0;
for (int i = 1; i <= mxK; i++) {
cnt[i] = n + 5;
}
result = n + 5;
centroid_decomp(0);
return (result >= n ? -1: result);
}
/*int main() {
cin.tie(0)->sync_with_stdio(0);
int N, K; cin >> N >> K;
int H[N][2], L[N];
for (int i = 0, x, y; i < N - 1; i++) {
cin >> H[i][0] >> H[i][1] >> L[i];
}
cout << best_path(N, K, H, L) << endl;
return 0;
}*/
/*
4 3
0 1 1
1 2 2
1 3 4
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/
