#include <bits/stdc++.h> using namespace std; const int N = 200000 + 5; const int INF = 1e9; int n, k; int ans; vector<pair<int,int>> adj[N]; unordered_map<int,int> best[N]; void dfs(int u, int p) { best[u][0] = 0; // độ dài 0, 0 cạnh for (auto [v, w] : adj[u]) { if (v == p) continue; dfs(v, u); // small-to-large if (best[v].size() > best[u].size()) best[u].swap(best[v]); // tìm đường ghép đủ k for (auto [len, cnt] : best[v]) { int need = k - w - len; if (need < 0) continue; if (best[u].count(need)) { ans = min(ans, best[u][need] + cnt + 1); } } // gộp map for (auto [len, cnt] : best[v]) { int nl = len + w; if (nl > k) continue; if (!best[u].count(nl)) best[u][nl] = cnt + 1; else best[u][nl] = min(best[u][nl], cnt + 1); } best[v].clear(); } } /* ===== IOI INTERFACE ===== */ int best_path(int _n, int _k, int H[][2], int L[]) { n = _n; k = _k; ans = INF; for (int i = 0; i < n; i++) { adj[i].clear(); best[i].clear(); } for (int i = 0; i < n - 1; i++) { int u = H[i][0]; int v = H[i][1]; int w = L[i]; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } dfs(0, -1); return (ans == INF ? -1 : ans); }