#include "race.h" #include <bits/stdc++.h> using namespace std; const int NN = 2e5 + 5; const int oo = 1e9; int n, k; vector<array<int, 2>> adj[NN]; struct CentroidDecomposition { vector<int> sub; vector<bool> removed; vector<int> mn; vector<int> touched; void init(int n) { sub.assign(n + 1, 0); removed.assign(n + 1, false); mn.assign(k + 1, oo); } int getsub(int u, int p) { sub[u] = 1; for (auto &[v, w] : adj[u]) { if (v != p && !removed[v]) sub[u] += getsub(v, u); } return sub[u]; } int find_centroid(int u, int p, int half) { for (auto &[v, w] : adj[u]) { if (v != p && !removed[v] && sub[v] > half) return find_centroid(v, u, half); } return u; } void getdist(int u, int p, int d, int we, vector<array<int, 2>> &dist) { if (we > k) return; dist.push_back({we, d}); for (auto &[v, w] : adj[u]) { if (v != p && !removed[v]) getdist(v, u, d + 1, we + w, dist); } } int solveK(int centroid) { int res = oo; touched.clear(); mn[0] = 0; touched.push_back(0); for (auto &[v, w0] : adj[centroid]) { if (removed[v]) continue; vector<array<int, 2>> dist; getdist(v, centroid, 1, w0, dist); for (auto &[we, d] : dist) { if (we <= k && mn[k - we] != oo) { res = min(res, mn[k - we] + d); } } for (auto &[we, d] : dist) { if (we <= k && d < mn[we]) { if (mn[we] == oo) touched.push_back(we); mn[we] = d; } } } for (int x : touched) mn[x] = oo; return res; } int solve(int u) { int sz = getsub(u, -1); int centroid = find_centroid(u, -1, sz >> 1); int res = solveK(centroid); removed[centroid] = true; for (auto &[v, w] : adj[centroid]) { if (!removed[v]) res = min(res, solve(v)); } removed[centroid] = false; return res; } }; int best_path(int N, int K, int H[][2], int L[]) { n = N; k = K; for (int i = 1; i <= n; ++i) adj[i].clear(); for (int i = 0; i < n - 1; ++i) { int u = H[i][0] + 1; int v = H[i][1] + 1; adj[u].push_back({v, L[i]}); adj[v].push_back({u, L[i]}); } CentroidDecomposition cd; cd.init(n + 5); int res = cd.solve(1); return (res == oo ? -1 : res); }