#include "race.h"
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
#define ff first
#define ss second
ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll maxN = 200507;
const ll LG = 18;
ll n, m, k;
set<pair<ll, ll>>g[maxN];
ll sz[maxN];
ll ans = INF;
map<ll, ll>cnt;
void dfs(ll v, ll par = -1) {
sz[v] = 1;
for (auto to : g[v]) {
if (to.ff != par) {
dfs(to.ff, v);
sz[v] += sz[to.ff];
}
}
}
ll centroid(ll v, ll size, ll par = -1) {
for (auto to : g[v]) {
if (to.ff != par && sz[to.ff] > size / 2) {
return centroid(to.ff, size, v);
}
}
return v;
}
void upd_ans(ll v, ll dpt, ll size, ll cur, ll par = -1) {
if (dpt <= k) {
//cout << dpt << " ";
if (k == dpt) {
ans = min(ans, cur);
//cout << "E ARECI HETO?\n";
}
else {
ans = min(ans, (cnt[k - dpt] == 0 ? INF : cnt[k - dpt]) + cur);
}
}
for (auto to : g[v]) {
if (to.ff != par) {
upd_ans(to.ff, dpt + to.ss, size, cur + 1, v);
}
}
}
void upd_cnt(ll v, ll dpt, ll cur, ll par = -1) {
if (dpt != 0) {
//cout << dpt << " ";
if (cnt[dpt] == 0) {
cnt[dpt] = cur;
}
else {
cnt[dpt] = min(cnt[dpt], cur);
}
//cout << v << ": " << dpt << ": " << cnt[dpt] << endl;
}
for (auto to : g[v]) {
if (to.ff != par) {
upd_cnt(to.ff, dpt + to.ss, cur + 1, v);
}
}
}
void mshak(ll c, ll size) {
//cout << "MSHAKUM ENQ: " << c << endl;
cnt.clear();
for (auto to : g[c]) {
upd_ans(to.ff, to.ss, size, 1, c);
upd_cnt(to.ff, to.ss, 1, c);
}
/*for (auto x : cnt) {
if(x.ff==k)cout << x.ff << ": " << x.ss << endl;
}*/
}
void cntr_dec(ll v, ll par = -1) {
dfs(v, par);
ll c = centroid(v, sz[v], par);
mshak(c, sz[v]);
set<pair<ll, ll>>g_copy(g[c]);
for (auto to : g_copy) {
g[c].erase(to);
g[to.ff].erase({ c,to.ss });
cntr_dec(to.ff, c);
}
}
int best_path(int NN, int K, int H[][2], int L[]) {
n = NN;
k = K;
for (int i = 0; i < n - 1; i++) {
g[H[i][0]].insert({ H[i][1],L[i] });
g[H[i][1]].insert({ H[i][0],L[i] });
}
cntr_dec(1);
return (ans == INF ? -1 : ans);
}
/// ---- - -------- ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - -------- ------ -------- -- - - -
