#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200000;
vector<pair<int, int> > graph[MAX_N];
set<pair<long long, int> > chains[MAX_N];
long long lazy[MAX_N];
int lazyedge[MAX_N];
int rez = MAX_N + 1;
int subtree[MAX_N];
void predfs(int nod, int papa = -1) {
subtree[nod]++;
for(auto it: graph[nod])
if(it.first != papa) {
predfs(it.first, nod);
subtree[nod] += subtree[it.first];
}
}
void solvedfs(int nod, int k, int papa = -1) {
int heavySon = -1;
for(auto it: graph[nod])
if(it.first != papa && (heavySon == -1 || (heavySon != -1 && subtree[it.first] > subtree[heavySon])))
heavySon = it.first;
for(auto it: graph[nod])
if(it.first != papa) {
solvedfs(it.first, k, nod);
lazy[it.first] += it.second;
lazyedge[it.first]++;
}
if(heavySon != -1) {
// Toarna chestii in heavySon
chains[nod].swap(chains[heavySon]);
swap(lazy[nod], lazy[heavySon]);
swap(lazyedge[nod], lazyedge[heavySon]);
for(auto it: graph[nod])
if(it.first != papa && it.first != heavySon) {
for(auto ch: chains[it.first]) {
set<pair<long long, int> >::iterator lb;
lb = chains[nod].lower_bound(make_pair(k - (ch.first + lazy[it.first]) - lazy[nod], -MAX_N-1));
if(lb != chains[nod].end() && lb->first + ch.first + lazy[it.first] + lazy[nod] == k)
rez = min(rez, ch.second + lb->second + lazyedge[it.first] + lazyedge[nod]);
}
for(auto ch: chains[it.first]) {
chains[nod].insert(make_pair(ch.first + lazy[it.first] - lazy[nod], ch.second + lazyedge[it.first] - lazyedge[nod]));
}
}
}
set<pair<long long, int> >::iterator lb;
lb = chains[nod].lower_bound(make_pair(k - lazy[nod], -MAX_N-1));
if(lb != chains[nod].end() && lb->first + lazy[nod] == k)
rez = min(rez, lb->second + lazyedge[nod]);
chains[nod].insert(make_pair(-lazy[nod], -lazyedge[nod]));
}
int best_path(int N, int K, int H[][2], int L[]) {
for(int i = 0; i < N - 1; ++i)
for(int j = 0; j < 2; ++j)
graph[H[i][j]].push_back(make_pair(H[i][0] ^ H[i][1] ^ H[i][j], L[i]));
predfs(0);
solvedfs(0, K);
if(rez == MAX_N + 1)
return -1;
return rez;
}
