#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
#define f first
#define s second
const int maxn = 200001;
vector<pii> adj[maxn];
map<ll, ll> info[maxn];
ll dist[maxn], sum[maxn];
int N;
ll K;
ll ret = LLONG_MAX;
void sack(int u, int p) {
vector<int> children;
for (auto &edge : adj[u]) {
if (edge.f == p) continue;
children.push_back(edge.f);
}
for (int v : children) {
sack(v, u);
}
int largest = -1;
for (int v : children) {
if (largest == -1 || info[v].size() > info[largest].size()) {
largest = v;
}
}
if (largest != -1) {
swap(info[u], info[largest]);
}
if (info[u].find(sum[u]) == info[u].end()) {
info[u][sum[u]] = dist[u];
} else {
info[u][sum[u]] = min(info[u][sum[u]], dist[u]);
}
ll target = 2 * sum[u] + K;
for (int v : children) {
if (v == largest) continue;
for (auto &kv : info[v]) {
ll s_val = kv.f;
ll d_val = kv.s;
auto it = info[u].find(target - s_val);
if (it != info[u].end()) {
ll candidate = it->s + d_val - 2 * dist[u];
if (candidate < ret) {
ret = candidate;
}
}
}
for (auto &kv : info[v]) {
ll s_val = kv.f;
ll d_val = kv.s;
auto it = info[u].find(s_val);
if (it == info[u].end()) {
info[u][s_val] = d_val;
} else {
it->s = min(it->s, d_val);
}
}
info[v].clear();
}
}
int best_path(int n, int k, int edges[][2], int weights[]) {
N = n;
K = k;
ret = LLONG_MAX;
for (int i = 0; i < n; i++) {
adj[i].clear();
info[i].clear();
}
for (int i = 0; i < n-1; i++) {
int u = edges[i][0];
int v = edges[i][1];
int w = weights[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<int> parent(n, -1);
stack<int> st;
st.push(0);
dist[0] = 0;
sum[0] = 0;
parent[0] = -1;
while (!st.empty()) {
int u = st.top();
st.pop();
for (auto &edge : adj[u]) {
int v = edge.f;
ll w = edge.s;
if (v == parent[u]) continue;
parent[v] = u;
sum[v] = sum[u] + w;
dist[v] = dist[u] + 1;
st.push(v);
}
}
sack(0, -1);
if (ret == LLONG_MAX) {
return -1;
}
return (int)ret;
}
