#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
vector<pair<int, int>> adj[MAXN];
bool vis[MAXN];
vector<int> comp;
int sz[MAXN];
int n, k;
void dfs(int v) {
vis[v] = true; sz[v] = 1;
for (auto& [viz, w] : adj[v]) {
if (vis[viz]) continue;
dfs(viz);
sz[v] += sz[viz];
}
}
int find_centroid(int v, int pai) {
// cout << "buscando centroid " << v << endl;
pair<int, int> mx = {v, 0};
for (auto& [viz, w] : adj[v]) {
if (viz == pai) continue;
if (mx.second < sz[viz]) mx = {viz, sz[viz]};
}
if (mx.second <= n / 2) {
// cout << "é" << v <<endl;
return v;
}
return find_centroid(mx.first, v);
}
map<int, int> sub_dist;
void get_dist(int v, int root, int dist, int depth) {
vis[v] = true;
comp.push_back(v);
if (sub_dist.count(dist) == 0) sub_dist[dist] = depth;
else sub_dist[dist] = min(sub_dist[dist], depth);
for (auto& [viz, w] : adj[v]) {
if (viz == root or vis[viz]) continue;
get_dist(viz, root, dist + w, depth+1);
}
}
int ans = 1e8;
void decomp(int v, int last_centroid=-1) {
int centroid = find_centroid(v, last_centroid);
// if (centroid == 8) cout << centroid << " é centroid decompondo" << v << endl;
map<int, vector<pair<int, int>>> dists;
for (auto& [viz, w] : adj[centroid]) {
if (viz == last_centroid) continue;
decomp(viz, centroid);
get_dist(viz, centroid, w, 1);
for (auto& [d, depth] : sub_dist) {
dists[d].push_back({depth, viz});
}
for (int v : comp) vis[v] = false;
comp.clear();
sub_dist.clear();
}
for (auto it = dists.begin(); it != dists.end(); it++) {
sort((it->second).begin(), (it->second).end());
}
if (!dists[k].empty()) ans = min(ans, dists[k][0].first);
for (auto& [viz, w] : adj[centroid]) {
if (viz == last_centroid) continue;
get_dist(viz, centroid, w, 1);
for (auto& [d, depth] : sub_dist) {
for (int i=0; i<min(2, (int)dists[k-d].size()); i++) {
if (dists[k-d][i].second == viz) continue;
ans = min(ans, dists[k-d][i].first + depth);
}
}
for (int v : comp) vis[v] = false;
comp.clear();
sub_dist.clear();
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N; k = K;
for (int i=0; i<N-1; i++) {
int u = H[i][0], v = H[i][1];
int w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(0);
for (int v=0; v<n; v++) vis[v] = false;
decomp(0);
return (ans == (int)1e8 ? -1 : ans);
}
