#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int oo = 1e9;
int n, k;
vector<array<int, 2>> adj[N];
struct CentroidDecomposition {
vector<int> sub;
vector<bool> removed;
vector<int> mn;
void init(int n) {
sub.assign(n + 1, 0);
mn.assign(k + 1, oo);
removed.assign(n + 1, false);
}
int getsub(int u, int p) {
sub[u] = 1;
for (auto &[v, w] : adj[u]) {
if (v != p && !removed[v]) sub[u] += getsub(v, u);
}
return sub[u];
}
int find(int u, int p, int half) {
for (auto &[v, w] : adj[u]) {
if (v != p && !removed[v] && sub[v] > half) return find(v, u, half);
}
return u;
}
void getdist(int u, int p, int d, int we, vector<array<int, 2>> &dist) {
dist.push_back({d, we});
for (auto &[v, w] : adj[u]) {
if (v != p && !removed[v]) getdist(v, u, d + 1, we + w, dist);
}
}
int solveK(int centroid, int treesize) {
int res = oo;
for (auto &[v, w] : adj[centroid]) {
if (removed[v]) continue;
vector<array<int, 2>> dist;
getdist(v, centroid, 1, w, dist);
for (auto &[d, w] : dist) {
if (w > k) {
continue;
}
res = min(res, mn[k - w] + 1);
}
for (auto &[d, w] : dist) {
if (w <= k) mn[w] = min(mn[w], d);
}
}
fill(mn.begin(), mn.begin() + (treesize >> 1) + 1, oo);
return res;
}
int solve(int u) {
int centroid = find(u, -1, getsub(u, -1) >> 1);
int res = solveK(centroid, sub[u]);
removed[centroid] = true;
for (auto &[v, w] : adj[centroid]) {
if (!removed[v]) res = min(res, solve(v));
}
return res;
}
};
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];
++u, ++v;
adj[u].push_back({v, L[i]});
adj[v].push_back({u, L[i]});
}
CentroidDecomposition cd;
cd.init(n + 5);
int res = cd.solve(1);
return (res == oo ? -1 : res);
}
/*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@}()))(([]}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%{]()<>>>^><>>><>><<<<(#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@{})<<>**+++**+*^++*^^^^^^<<)#@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@%(^*>+++====~~~+=~~+==*=+*+*<^^[@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@#<**+^==+*~~----=+---=~-~~~~~==>**<}@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@{([*^==~~==-----:-=---:-:------~~>*++}@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@<^<=~~-~~-:::::::~:::::::::---=~=+=^^{@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@%>))^=~---::::::.:.::.:..-::::::-~~^=+)){@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@##))^~~~-~+::::.......:..:.-:::-:=~+<+>]{%@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@%(()*=*~*=^:~:-.::.::.:....~::::-=~+)<^(%@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@}}()>+***<^-^-~:~::*-.~::::=----=*=^>))]{@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@%@]])<<^)*])~<~=:++-)+-^---:*~--~+><>)))[%@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@%[{()]<])%<=<+>-><=)>~)=~=~^==~=*<<)<(){@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@%@@]([){[]})(*)+)]*]]=]]=++^*+~^)(<)[(]#@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@}{(<<<>)]}>()]}]{[<))^*)>^**<})([]<}%@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@<>^^^^)]<*()[]]<>>)<^]<<<>(]>(}[}@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@<>^^^([>>^^^^^>^^^^>>>)()<<>]]]@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@[>^>[[)>^^^^^^^^^^^^^><<]<>><]@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@#>>^]]>^^^^^^^^^^^^^^>^^(>{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@(>>>({[}[^^^^^^^^^^^^^^>[%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@(>><>>^^^^^^^^^^^^^^^>){%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@%<>]><>^^^^^^^^^^^^><]}}}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@{<><])<><<^^^^^>)[}}{[[}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@{[>>^^^^^^^^>)[{}}}}}[}{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%}[>>^^^^>){}}}}}}}}}}[}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@{}}#{}[}}}}}}}}}}}}}()%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@}}}}{}}}}}}}}}}}}}]>>(%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%{}}}{}}}}}}}}}}}})>>>]}{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@%{{}}}}}}}}}}}}]<]<>>>>>[}%@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@{}}}}}}{[[}}}[)>>))>>>>>><[%@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@{}}}}}}}}))(>>>>>[>>>>>>>><{@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@{}}}})>>[{<>>>^^()<<>>>>>><}@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@{)<<>><[}>>>>>[<](>>><<}@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%{]<<(]>><}])[{#%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/
