#include <bits/stdc++.h> #include "race.h" #define F first #define S second #define SZ(x) ((int)(x).size()) #define ALL(x) x.begin(), x.end() using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<ll>; using vvi = vector<vi>; using vvl = vector<vl>; using pii = pair<int, int>; using pll = pair<ll, ll>; using vii = vector<pii>; using vll = vector<pll>; static const int INF = 0x3f3f3f3f; static const int maxn = 200005; static const int maxk = 1000005; static int n, k; static array<int, maxn> sz; static array<int, maxk> mn; static array<vii, maxn> adj; static bitset<maxn> removed; static void build_size(int u, int p) { sz[u] = 1; for (auto &[v, w]: adj[u]) { if (v == p || removed[v]) continue; build_size(v, u); sz[u] += sz[v]; } } static int find_centroid(int u, int p, int tree_size) { for (auto &[v, w]: adj[u]) { if (v == p || removed[v]) continue; if (sz[v] > tree_size / 2) return find_centroid(v, u, tree_size); } return u; } static int dfs_get(int u, int p, int dep, int dis) { if (dis > k) return INF; int ans = min(dep + mn[k - dis], INF); for (auto &[v, w]: adj[u]) { if (v == p || removed[v]) continue; ans = min(ans, dfs_get(v, u, dep + 1, dis + w)); } return ans; } static void dfs_upd(int u, int p, int dep, int dis, vi& used) { if (dis > k) return; mn[dis] = min(mn[dis], dep); used.push_back(dis); for (auto &[v, w]: adj[u]) { if (v == p || removed[v]) continue; dfs_upd(v, u, dep + 1, dis + w, used); } } static int centroid_decomposition(int root) { build_size(root, -1); int centroid = find_centroid(root, -1, sz[root]); int ans = INF; vi used; for (auto &[v, w]: adj[centroid]) { if (removed[v]) continue; ans = min(ans, dfs_get(v, centroid, 1, w)); dfs_upd(v, centroid, 1, w, used); } for (int x: used) if (x > 0) mn[x] = INF; removed[centroid] = 1; for (auto& [v, w]: adj[centroid]) { if (removed[v]) continue; ans = min(ans, centroid_decomposition(v)); } return ans; } int best_path(int _n, int _k, int edges[][2], int W[]) { n = _n, k = _k; for (int i = 0; i < n - 1; i++) { int u = edges[i][0], v = edges[i][1]; adj[u].push_back({v, W[i]}); adj[v].push_back({u, W[i]}); } for (int i = 1; i <= k; i++) { mn[i] = INF; } int ans = centroid_decomposition(0); if (ans >= INF) ans = -1; return ans; }