#include <bits/stdc++.h> using namespace std; static const int MAXN = 200000; vector<pair<int,int>> g[MAXN + 5]; int num[MAXN + 5], del[MAXN + 5]; int tot, K; int ans; vector<int> min_edge; vector<int> touched; void calc_num(int u, int p) { tot++; num[u] = 1; for (auto [v, w] : g[u]) { if (v == p || del[v]) continue; calc_num(v, u); num[u] += num[v]; } } int find_cen(int u, int p) { for (auto [v, w] : g[u]) { if (v == p || del[v]) continue; if (num[v] > tot / 2) return find_cen(v, u); } return u; } void dfs_collect(int u, int p, int wei, int dep, vector<pair<int,int>> &deps) { deps.push_back({wei, dep}); for (auto [v, w] : g[u]) { if (v == p || del[v]) continue; dfs_collect(v, u, wei + w, dep + 1, deps); } } void decompose(int u) { tot = 0; calc_num(u, -1); int cen = find_cen(u, -1); del[cen] = 1; for (auto [v, w] : g[cen]) { if (del[v]) continue; vector<pair<int,int>> deps; dfs_collect(v, cen, w, 1, deps); for (auto [wei, dep] : deps) { if (wei <= K && min_edge[K - wei] != INT_MAX) { ans = min(ans, dep + min_edge[K - wei]); } } for (auto [wei, dep] : deps) { if (wei <= K) { if (min_edge[wei] == INT_MAX) touched.push_back(wei); min_edge[wei] = min(min_edge[wei], dep); } } } for (int x : touched) min_edge[x] = INT_MAX; touched.clear(); for (auto [v, w] : g[cen]) { if (!del[v]) decompose(v); } } int best_path(int N, int K_input, int H[][2], int L[]) { K = K_input; ans = INT_MAX; for (int i = 0; i < N; i++) { g[i].clear(); del[i] = 0; } for (int i = 0; i < N - 1; i++) { int u = H[i][0]; int v = H[i][1]; int w = L[i]; g[u].push_back({v, w}); g[v].push_back({u, w}); } min_edge.assign(K + 1, INT_MAX); min_edge[0] = 0; // đường rỗng tại centroid decompose(0); return (ans == INT_MAX ? -1 : ans); }