#include <bits/stdc++.h>
using namespace std;
struct node {
list<pair<node*, int>> l;
int subtree = 1;
set<pair<long long, int>>* s = nullptr;
};
int m = 1e9, k;
void dfs(node* n, node* parent, long long sum, int depth){
int ms = -1;
node* mc = nullptr;
for(auto p : n->l){
if(p.first != parent){
dfs(p.first, n, sum + p.second, depth + 1);
n->subtree += p.first->subtree;
if(p.first->subtree > ms){
ms = p.first->subtree;
mc = p.first;
}
}
}
if(ms == -1){
n->s = new set<pair<long long, int>>();
} else {
n->s = mc->s;
}
n->s->insert({sum, depth});
for(auto p : n->l){
if(p.first != parent && p.first != mc){
for(auto f : *p.first->s){
long long target = k + 2 * sum - f.first;
auto it = n->s->lower_bound({target, 0});
if(it != n->s->end() && it->first == target){
if(f.second + it->second - 2 * depth < m) m = f.second + it->second - 2 * depth;
}
}
for(auto f : *p.first->s){
n->s->insert(f);
}
}
}
auto it = n->s->lower_bound({k + sum, 0});
if(it != n->s->end() && it->first == k + sum){
if(depth + it->second - 2 * depth < m) m = depth + it->second - 2 * depth;
}
}
int best_path(int N, int K, int H[][2], int L[]){
k = K;
node nodes[N+1];
int u, v, c;
for(int i = 0;i < N-1;i++){
u = H[i][0];
v = H[i][1];
c = L[i];
nodes[u].l.push_back({&nodes[v], c});
nodes[v].l.push_back({&nodes[u], c});
}
dfs(&nodes[1], nullptr, 0, 0);
map<set<pair<long long, int>>*, bool> del;
for(int i = 1;i <= N;i++) {
if(del[nodes[i].s]) continue;
delete nodes[i].s;
del[nodes[i].s] = true;
}
return m == 1e9 ? -1 : m;
}
