#include <bits/stdc++.h> using namespace std; // KACTL TEMPLATE #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } const int N = 2E5 + 5; const int D = 1E6 + 5; int sz[N]; bool vis[N]; int dis[D]; vector<pii> adj[N]; int best_path(int n, int k, int h[][2], int l[]) { for (int i = 0; i < n - 1; i++) { int u = h[i][0]; int v = h[i][1]; int w = l[i]; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } int ans = -1; auto dfs = [&](auto &&self, int u, int p) -> void { sz[u] = 1; for (auto &[v, w]: adj[u]) { if (vis[v] || v == p) { continue; } self(self, v, u); sz[u] += sz[v]; } }; auto get_root = [&](auto &&self, int u, int p, int &s) -> int { for (auto &[v, w]: adj[u]) { if (vis[v] || v == p) { continue; } if (sz[v] * 2 > s) { return self(self, v, u, s); } } return u; }; auto calc = [&](auto &&self, int u, int d, int s, vector<pii> &add) -> void { if (s > k) { return; } add.emplace_back(s, d); if (dis[k - s] != -1) { if (ans == -1) { ans = dis[k - s] + d; } else { ans = min(ans, dis[k - s] + d); } } for (auto &[v, w]: adj[u]) { if (vis[v]) { continue; } self(self, v, d + 1, s + w, add); } }; auto solve = [&](auto &&self, int u) -> void { dfs(dfs, u, -1); int r = get_root(get_root, u, -1, sz[u]); vis[r] = true; fill(dis, dis + k + 1, -1); dis[0] = 0; for (auto &[v, w]: adj[r]) { if (vis[v]) { continue; } vector<pii> add; calc(calc, v, 1, w, add); for (auto &[s, d]: add) { if (dis[s] == -1) { dis[s] = d; } else { dis[s] = min(dis[s], d); } } } for (auto &[v, w]: adj[r]) { if (!vis[v]) { self(self, v); } } }; solve(solve, 0); return ans; }