#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5;
const ll INFLL = 1e18;
const int INF = 1e9;
int mx[MAXN], subSz[MAXN], mnDepth[MAXN];
vector<pair<int, ll>> adj[MAXN];
int depth[MAXN];
ll depthW[MAXN], allDepthW[2*MAXN];
map<int, int> mpDepthW;
vector<int> sub[MAXN];
int k;
int ans = INF;
void dfsPre(int v, int pai) {
subSz[v] = 1;
for (auto [viz, w] : adj[v]) {
if (viz == pai) continue;
depthW[viz] = depthW[v] + w;
depth[viz] = depth[v] + 1;
allDepthW[viz] = depthW[viz];
dfsPre(viz, v);
if (mx[v] == -1 or subSz[viz] > subSz[mx[v]])
mx[v] = viz;
subSz[v] += subSz[viz];
}
}
void add(int v, vector<int> newNodes) {
for (int i : newNodes) {
sub[v].push_back(i);
int dep = mpDepthW[depthW[i]];
mnDepth[dep] = min(mnDepth[dep], depth[i]);
}
}
void dfs(int v, int pai, bool clear) {
for (auto [viz, w] : adj[v]) {
if (viz == pai or viz == mx[v]) continue;
dfs(viz, v, true);
}
if (mx[v] != -1) {
dfs(mx[v], v, false);
swap(sub[v], sub[mx[v]]);
}
if (mpDepthW.count(k + depthW[v]) != 0)
ans = min(ans, mnDepth[mpDepthW[k+depthW[v]]] - depth[v]);
// cout << v << ' ' << ans << '\n';
add(v, {v});
for (auto [viz, w] : adj[v]) {
if (viz == pai or viz == mx[v]) continue;
for (int i : sub[viz]) {
ll x = depthW[i] - depthW[v];
if (mpDepthW.count(k - x + depthW[v]) == 0) continue;
ans = min(ans, depth[i] - depth[v] + mnDepth[mpDepthW[k-x + depthW[v]]] - depth[v]);
}
add(viz, sub[viz]);
sub[viz].clear();
}
if (clear) {
for (int i : sub[v]) {
mnDepth[mpDepthW[depthW[i]]] = INF;
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
int n = N;
k = K;
for (int i=0; i<n; i++) {
mnDepth[i] = INF;
mx[i] = -1;
}
for (int i=0; i<n-1; i++) {
int u = H[i][0], v = H[i][1]; ll w = L[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
dfsPre(0, -1);
// for (int i=0; i<n; i++) cout << depthW[i] << ' ';
// cout << '\n';
sort(allDepthW, allDepthW + n);
for (int i=0; i<n; i++) mpDepthW[allDepthW[i]] = i;
dfs(0, -1, false);
if (ans == INF) return -1;
return ans;
}
