#include "race.h" #include "bits/stdc++.h" using namespace std; typedef long long ll; #define all(x) (x).begin(), (x).end() #define isz(x) (int)(x.size()) const int sz = 500200, inf = 1000000000; struct CentroidDecomposition { vector<vector<array<int, 2>>> g; vector<int> sz, mn; vector<bool> removed; vector<vector<array<int, 2>>> dis; int n, k, ans; CentroidDecomposition(int n, vector<vector<array<int, 2>>> &g, int k) : n(n) , g(g), k(k) { removed.assign(n + 1, false); sz.assign(n + 1, 0); dis.resize(n + 1); mn.assign(k + 1, inf); mn[0] = 0; ans = inf; } int getSubsize(int u, int p = -1) { sz[u] = 1; for (auto &[v, w] : g[u]) if (!removed[v] && v != p) sz[u] += getSubsize(v, u); return sz[u]; } int findCentroid(int u, int half, int p = -1) { for (auto &[v, w] : g[u]) { if (v != p && !removed[v] && sz[v] > half) return findCentroid(v, half, u); } return u; } void dfs(int u, int centroid, int dep = 0, int weight = 0, int p = -1) { if (weight > k) return; ans = min(ans, dep + mn[k - weight]); dis[centroid].push_back({dep, weight}); for (auto &[v, w] : g[u]) { if (removed[v] || v == p) continue; dfs(v, centroid, dep + 1, weight + w, u); } } int build(int v = 1) { // TODO inside int centroid = findCentroid(v, getSubsize(v) / 2); mn.resize(n + 1, inf); removed[centroid] = true; for (auto &[u, w] : g[centroid]) { if (removed[u]) continue; dfs(u, centroid, 1, w); for (auto [dep, weight] : dis[centroid]) { mn[weight] = min(mn[weight], dep); } dis[centroid].clear(); } for (auto &[u, w] : g[centroid]) { if (removed[u]) continue; build(u); } return centroid; } }; int best_path(int N, int K, int H[][2], int L[]) { int n = N, k = K; vector<vector<array<int, 2>>> g(n + 1); for (int i = 0; i < n - 1; i++) { H[i][0]++, H[i][1]++; g[H[i][0]].push_back({H[i][1], L[i]}); g[H[i][1]].push_back({H[i][0], L[i]}); } CentroidDecomposition c(n, g, k); c.build(); return (c.ans == inf ? -1 : c.ans); }