#include <bits/stdc++.h> #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } using namespace std; int best_path(int n, int k, int h[][2], int l[]) { vector<vector<pair<int, int>>> g(n); for(int i = 0; i < n - 1; ++i) { int u = h[i][0], v = h[i][1]; g[u].emplace_back(v, l[i]); g[v].emplace_back(u, l[i]); } int ans = n; vector<bool> del(n, false); vector<int> sz(n, 0); function<void(int, int)> get_sz = [&](int u, int p) -> void { sz[u] = 1; for(pair<int, int> e : g[u]) { int v = e.first; if(v == p || del[v]) continue; get_sz(v, u); sz[u] += sz[v]; } }; function<int(int, int, int)> get_cen = [&](int u, int p, int tot) -> int { for(pair<int, int> e : g[u]) { int v = e.first; if(v == p || del[v]) continue; if(sz[v] > tot / 2) return get_cen(v, u, tot); } return u; }; map<long long, int> mp; function<void(int, int, int, long long, bool)> dfs = [&](int u, int p, int depth, long long dist, bool sus) { if(!sus) { if(mp.count(k - dist)) ans = min(ans, depth + mp[k - dist]); } else { if(mp.count(dist)) mp[dist] = min(mp[dist], depth); else mp[dist] = depth; } for(pair<int, int> e : g[u]) { int v = e.first, w = e.second; if(v == p || del[v]) continue; dfs(v, u, depth + 1, dist + w, sus); } }; function<void(int)> centroid = [&](int u) -> void { get_sz(u, -1); int cen = get_cen(u, -1, sz[u]); del[cen] = true; mp.clear(); mp[0] = 0; for(pair<int, int> e : g[cen]) { int v = e.first, w = e.second; if(del[v]) continue; dfs(v, cen, 1, w, false); dfs(v, cen, 1, w, true); } for(pair<int, int> e : g[cen]) { int v = e.first; if(del[v]) continue; centroid(v); } }; centroid(1); if(ans >= n) ans = -1; return ans; } //int main() { // ios_base::sync_with_stdio(false); // cin.tie(0), cout.tie(0); // // file("A") else file("task"); // int n, k; // cin >> n >> k; // int h[n - 1][2], l[n - 1]; // for(int i = 0; i < n; ++i) { // int u, v, c; // cin >> u >> v >> c; // h[i][0] = u; // h[i][1] = v; // l[i] = c; // } // cout << best_path(n, k, h, l) << '\n'; // return 0; //}