#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
int n, k;
int ans;
vector<int> dep, distv, sz, bigchild;
vector<vector<int>> adj;
unordered_map<int,int> mp;
unordered_map<long long,int> wei;
void pre_dfs(int u, int p){
sz[u] = 1;
for(int v : adj[u]) if (v != p) {
dep[v] = dep[u] + 1;
distv[v] = distv[u] + wei[( (ll)u<<32 ) | v];
pre_dfs(v, u);
sz[u] += sz[v];
if (bigchild[u] < 0 || sz[v] > sz[ bigchild[u] ])
bigchild[u] = v;
}
}
void calc_down(int u, int p, int distlca, int deplca){
int want = k + 2*distlca - distv[u];
auto it = mp.find(want);
if (it != mp.end())
ans = min(ans, it->second + dep[u] - 2*deplca);
for(int v : adj[u]) if (v != p)
calc_down(v, u, distlca, deplca);
}
void add_down(int u, int p){
auto it = mp.find(distv[u]);
if (it == mp.end()) mp[distv[u]] = dep[u];
else it->second = min(it->second, dep[u]);
for(int v : adj[u]) if (v != p)
add_down(v, u);
}
void dfs(int u, int p, bool keep){
// xử lý các nhánh nhỏ trước
for(int v : adj[u]) if (v!=p && v!=bigchild[u])
dfs(v, u, false);
// rồi đến nhánh lớn
if (bigchild[u] >= 0)
dfs(bigchild[u], u, true);
// xử lý các nhánh nhỏ: kiểm tra + thêm vào map
for(int v : adj[u]) if (v!=p && v!=bigchild[u]) {
calc_down(v, u, distv[u], dep[u]);
add_down(v, u);
}
// cuối cùng tự xử lý u
// trước hết kiểm pair case chỉ 1 node
int want0 = k + distv[u];
auto it0 = mp.find(want0);
if (it0 != mp.end())
ans = min(ans, it0->second - dep[u]);
// sau đó thêm u
auto it1 = mp.find(distv[u]);
if (it1 == mp.end()) mp[distv[u]] = dep[u];
else it1->second = min(it1->second, dep[u]);
if (!keep) {
mp.clear();
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N; k = K;
adj.assign(n, {});
dep.assign(n,0); distv.assign(n,0);
sz.assign(n,0); bigchild.assign(n,-1);
// build
for(int i=0;i<n-1;i++){
int x=H[i][0], y=H[i][1];
adj[x].push_back(y);
adj[y].push_back(x);
wei[( (ll)x<<32 )|y] = L[i];
wei[( (ll)y<<32 )|x] = L[i];
}
ans = INF;
pre_dfs(0,-1);
// khởi tạo map với root
mp.clear();
mp[0] = 0; // dist[0]=0, dep[0]=0
dfs(0, -1, false);
return ans==INF? -1 : ans;
}
