#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define pb push_back
#define mp make_pair
const int mxN = 2e5+5, B = 24, inf = 2e9;
int n, k, root;
vii adj[mxN];
int sz[mxN];
int dis[mxN];
int wdis[mxN];
set<int> dp[mxN];
int p[mxN];
int r[mxN];
vi sons[mxN];
int up[B][mxN];
int lca(int u, int v) {
int a = dis[u];
int b = dis[v];
if (a < b) {
swap(u, v);
swap(a, b);
}
int dif = a-b;
for (int i = 0; i < B; i++) {
if (dif & (1<<i)) {
u = up[i][u];
}
}
a = b;
if (u == v) return u;
int l = 1;
int r = a;
while (l < r) {
int mid = (l+r)/2;
int x = u;
int y = v;
for (int i = 0; i < B; i++) {
if (mid & (1<<i)) {
x = up[i][x];
y = up[i][y];
}
}
if (x == y) r = mid;
else l = mid+1;
}
for (int i = 0; i < B; i++) {
if (l & (1<<i)) {
u = up[i][u];
}
}
return u;
}
void calcSz(int u, int par) {
sz[u] = 1;
for (auto &[v, w] : adj[u]) {
if (v == par || r[v]) continue;
calcSz(v, u);
sz[u] += sz[v];
}
}
int findCentroid(int u, int par, int siz) {
for (auto &[v, w] : adj[u]) {
if (v == par || r[v]) continue;
if (sz[v]*2 > siz) return findCentroid(v, u, siz);
}
return u;
}
void build(int u, int par) {
calcSz(u, -1);
int centroid = findCentroid(u, -1, sz[u]);
r[centroid] = 1;
p[centroid] = par;
if (par != -1) sons[par].push_back(centroid);
if (root == -1) root = centroid;
for (auto &[v, w] : adj[centroid]) {
if (r[v]) continue;
build(v, centroid);
}
}
void calcDis(int u, int par, int d, int wd) {
dis[u] = d;
wdis[u] = wd;
for (auto &[v, w] : adj[u]) {
if (v == par) continue;
up[0][v] = u;
calcDis(v, u, d+1, wd+w);
}
}
void calcDp(int u) {
for (int &v : sons[u]) {
int a = lca(u, v);
int d = wdis[u] + wdis[v] - wdis[a]*2;
dp[u].insert(d);
for (int dv : dp[v]) {
if (dv == 0) continue;
if (dv + d > k) break;
dp[u].insert(dv + d);
}
}
}
int findPath(int u, int d) {
if (d == 0) return u;
for (int &v : sons[u]) {
int a = lca(u, v);
int di = wdis[u] + wdis[v] - wdis[a]*2;
if (d-di == 0 || dp[v].find(d-di) != dp[v].end()) {
return findPath(v, d-di);
}
}
return 0; // never reached
}
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 x = H[i][0];
int y = H[i][1];
adj[x].pb(mp(y, L[i]));
adj[y].pb(mp(x, L[i]));
}
calcDis(0, -1, 0, 0);
build(0, -1);
calcDp(root);
for (int i = 1; i < B; i++) {
for (int j = 0; j < n; j++) {
if ((1<<i) > dis[j]) continue;
up[i][j] = up[i-1][up[i-1][j]];
}
}
int mn = inf;
for (int i = 0; i < n; i++) {
auto it = dp[i].find(k);
if (it != dp[i].end()) {
int v = findPath(i, k);
int a = lca(i, v);
mn = min(mn, dis[i] + dis[v] - dis[a]*2);
}
int x = p[i];
int son = i;
while (x != -1) {
for (int &v : sons[x]) {
if (v == son) continue;
int a = lca(i, v);
int d = dis[i] + dis[v] - dis[a]*2;
int wd = wdis[i] + wdis[v] - wdis[a]*2;
if (wd > k) continue;
if (wd == k) {
mn = min(mn, d);
continue;
}
auto it2 = dp[v].find(k-wd);
if (it2 != dp[v].end()) {
int y = findPath(v, k-wd);
int z = lca(v, y);
mn = min(mn, d + dis[v] + dis[y] - dis[z]*2);
}
}
son = x;
x = p[x];
}
}
return mn == inf ? -1 : mn;
}
