#include<bits/stdc++.h>
#include "race.h"
#define forn(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;
typedef vector<int> vi;
const int MAXN = 2e5 + 20;
typedef pair<int,int> pii;
int sz[MAXN];
bool vis[MAXN];
vector<vi> adj;
int _K;
map<pii, int> edg;
const int INF = 1e8;
void dfs_sz(int u, int pa) {
// cout << "dfs_sz: " << u << ' ' << pa << endl;
sz[u] = 1;
for(int v : adj[u]) if(v != pa && !vis[v]) {
dfs_sz(v, u);
sz[u] += sz[v];
}
}
void go_children(int u, int pa, map<int, int>& curr, int depth = 1, int dis = 0) {
int val = edg[{min(u, pa), max(u, pa)}] + dis;
if(!curr.count(val)) curr[val] = INF;
curr[val] = min(curr[val], depth);
for(int v : adj[u]) if(v != pa && !vis[v]) {
go_children(v, u, curr, depth + 1, val);
}
}
void merge_maps(map<int,int>& tot, map<int,int>& curr) {
for(auto& [val, cnt] : curr) {
if(!tot.count(val)) {
tot[val] = cnt;
}
tot[val] = min(tot[val], cnt);
}
}
int get_ans_curr(map<int,int>& tot, map<int,int>& curr) {
int ans = INF;
for(auto& [val, cnt] : curr) {
int need = _K - val;
if(tot.count(need)) {
ans = min(ans, tot[need] + cnt);
}
}
return ans;
}
int get_centroid(int u) {
// cout << "get_centroid: " << u << endl;
for(int v : adj[u]) if(!vis[v]) {
if(2*sz[v] > sz[u]) {
sz[u] -= sz[v];
sz[v] += sz[u];
return get_centroid(v);
}
}
return u;
}
int solve_centroid(int cen) {
map<int,int> tot;
int ans = INF;
for(int v : adj[cen]) if(!vis[v]) {
map<int,int> curr;
curr[0] = 0;
go_children(v, cen, curr);
ans = min(ans, get_ans_curr(tot, curr));
merge_maps(tot, curr);
}
return ans;
}
int solve(int u) {
dfs_sz(u, u);
int centroid = get_centroid(u);
// cout << "centroid: " << centroid << endl;
vis[centroid] = true;
int ans = solve_centroid(centroid);
for(int v : adj[centroid]) if(!vis[v]) {
ans = min(solve(v), ans);
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[]) {
_K = K;
adj.resize(N);
forn(i,N-1) {
int u = H[i][0];
int v = H[i][1];
adj[u].pb(v);
adj[v].pb(u);
edg[{min(u,v), max(u,v)}] = L[i];
}
int ans = solve(0);
if(ans == INF) return -1;
return ans;
}
