#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);
int N, K;
vector<vector<pair<int,int>>> adj;
vector<ll> sumv; // sum of weights from root to u
vector<int> depthv; // depth (number of edges) from root to u
vector<int> sz, heavy;
ll answer = INF;
// for DSU on tree
unordered_map<ll,int> mp;
int curRoot;
// 1) dfs1: tính sumv[], depthv[], sz[] và xác định heavy[u]
void dfs1(int u, int p){
sz[u] = 1;
heavy[u] = -1;
for (auto &[v,w] : adj[u]) if (v != p){
sumv[v] = sumv[u] + w;
depthv[v] = depthv[u] + 1;
dfs1(v, u);
if (heavy[u] == -1 || sz[v] > sz[ heavy[u] ])
heavy[u] = v;
sz[u] += sz[v];
}
}
// helper: cập nhật answer khi gặp node x với gốc curRoot
inline void query_node(int x){
ll need = (ll)K + 2*sumv[curRoot] - sumv[x];
auto it = mp.find(need);
if (it != mp.end())
answer = min(answer, (ll)depthv[x] + it->second - 2LL*depthv[curRoot]);
}
// helper: thêm node x vào mp (lưu depth nhỏ nhất)
inline void add_node(int x){
auto it = mp.find(sumv[x]);
if (it == mp.end()) mp[ sumv[x] ] = depthv[x];
else it->second = min(it->second, depthv[x]);
}
// traverse subtree of u:
// if doQuery==true: query each node x against current mp
// else : insert each node x into mp
void dfs_add(int u, int p, bool doQuery){
if (doQuery) query_node(u);
else add_node(u);
for (auto &[v,w] : adj[u]) if (v != p){
dfs_add(v, u, doQuery);
}
}
// 2) dfs2: DSU on tree chính
void dfs2(int u, int p, bool keep){
// 1) xử lý tất cả con nhỏ trước (clear xong)
for (auto &[v,w] : adj[u]) if (v != p && v != heavy[u])
dfs2(v, u, false);
// 2) xử lý con heavy, giữ lại mp
if (heavy[u] != -1)
dfs2(heavy[u], u, true);
// 3) merge các light subtrees vào mp, trước tiên query thỏa mãn, rồi insert
for (auto &[v,w] : adj[u]) if (v != p && v != heavy[u]){
curRoot = u;
dfs_add(v, u, true); // query mọi node trong subtree v
dfs_add(v, u, false); // rồi add tất cả vào mp
}
// 4) cuối cùng xử lý chính u
curRoot = u;
query_node(u);
add_node(u);
// 5) nếu không giữ thì clear hết
if (!keep)
mp.clear();
}
int best_path(int n, int k, int edges[][2], int weights[]){
N = n; K = k;
adj.assign(N, {});
sumv.assign(N, 0);
depthv.assign(N, 0);
sz.assign(N, 0);
heavy.assign(N, -1);
answer = INF;
mp.reserve(N*2);
// build graph
for (int i = 0; i < N-1; i++){
int u = edges[i][0], v = edges[i][1];
int w = weights[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
// 1) precompute sizes, heavy, sums, depths
dfs1(0, -1);
// 2) dsu on tree
dfs2(0, -1, false);
return (answer == INF ? -1 : (int)answer);
}
