// centroid_race.cpp
// Usage: implement best_path(N, K, H, L) function as IOI interface.
// This version returns minimal number of edges to get path length exactly K or -1.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INFLL = (ll)4e18;
struct Edge { int to; ll w; };
int Nglobal;
vector<vector<Edge>> G;
vector<int> subSz;
vector<char> removed;
ll BEST;
void dfs_size(int u, int p){
subSz[u] = 1;
for (auto &e : G[u]) if (e.to != p && !removed[e.to]){
dfs_size(e.to, u);
subSz[u] += subSz[e.to];
}
}
int find_centroid(int u, int p, int total){
for (auto &e : G[u]) if (e.to != p && !removed[e.to]){
if (subSz[e.to] > total/2) return find_centroid(e.to, u, total);
}
return u;
}
void collect_distances(int u, int p, ll dist, int edges, vector<pair<ll,int>> &out){
out.emplace_back(dist, edges);
for (auto &e : G[u]) if (e.to != p && !removed[e.to]){
collect_distances(e.to, u, dist + e.w, edges + 1, out);
}
}
void decompose(int start, ll K){
// compute subtree sizes and centroid
dfs_size(start, -1);
int c = find_centroid(start, -1, subSz[start]);
removed[c] = 1;
// map: distance -> minimal edges (for distances seen so far for this centroid)
unordered_map<ll,int> best;
best.reserve(1024);
best[0] = 0; // distance 0 at centroid with 0 edges
for (auto &e : G[c]){
if (removed[e.to]) continue;
vector<pair<ll,int>> vec;
collect_distances(e.to, c, e.w, 1, vec);
// First, try to match distances in vec with best
for (auto &pr : vec){
ll d = pr.first;
int ed = pr.second;
ll need = K - d;
auto it = best.find(need);
if (it != best.end()){
BEST = min(BEST, (ll)ed + it->second);
}
}
// Then merge vec into best (keep minimal edges for each distance)
for (auto &pr : vec){
ll d = pr.first;
int ed = pr.second;
auto it = best.find(d);
if (it == best.end() || ed < it->second) best[d] = ed;
}
}
// Recurse on subtrees
for (auto &e : G[c]){
if (!removed[e.to]) decompose(e.to, K);
}
}
int best_path(int N, ll K, int H[][2], int L[]){
Nglobal = N;
G.assign(N, {});
for (int i = 0; i < N-1; ++i){
int u = H[i][0], v = H[i][1];
ll w = (ll)L[i];
G[u].push_back({v, w});
G[v].push_back({u, w});
}
subSz.assign(N, 0);
removed.assign(N, 0);
BEST = INFLL;
decompose(0, K);
if (BEST >= INFLL) return -1;
return (int)BEST;
}
