#include <race.h>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define MAXN 200002
vii adjList[MAXN];
int treeSize[MAXN];
bool ign[MAXN];
int getSize(int node, int parent) {
int size = 1;
for(ii connection : adjList[node]) {
int adj = connection.first;
if(adj == parent) {
continue;
}
if(ign[adj]) {
continue;
}
size += getSize(adj,node) + connection.second;
}
treeSize[node] = size;
return size;
}
int getCentroid(int node, int parent, int fullSize) {
for(ii connection : adjList[node]) {
int adj = connection.first;
if(adj == parent) {
continue;
}
if(ign[adj]) {
continue;
}
if(treeSize[adj] * 2 > fullSize) {
int res = getCentroid(adj,node,fullSize);
//cout << "getCentroid(" << node << ") returned " << res << endl;
return res;
}
}
//cout << node << endl;
return node;
}
unordered_map<int,int> getPathLengths(int node, int parent,
int maxValue) {
unordered_map<int,int> results;
if(maxValue < 0) {
return results;
}
results[0] = 0;
for(ii connection : adjList[node]) {
int adj = connection.first;
int weight = connection.second;
if(adj == parent) {
continue;
}
if(ign[adj]) {
continue;
}
unordered_map<int,int> sub = getPathLengths(adj,node, maxValue - weight);
for(auto& it : sub) {
int total = weight + it.first;
if(results.count(total) == 0 || results[total] > (1 + it.second)) {
results[total] = 1 + it.second;
}
}
}
return results;
}
int k;
int best[1000002];
int auxBest[1000002];
int auxCur = 1;
int solveFor(int treeStart, int parent) {
//cerr << "solveFor " << treeStart << endl;
if(ign[treeStart]) {
return 2 * MAXN;
}
getSize(treeStart,parent);
int centroid = getCentroid(treeStart,parent,treeSize[treeStart]);
int childMin = MAXN * 2;
ign[centroid] = true;
++auxCur;
//cout << "starting cross node for " << treeStart << endl;
unordered_map<int,int> allResults;
allResults[0] = 0;
auxBest[0] = auxCur;
for(ii connection : adjList[centroid]) {
int adj = connection.first;
if(ign[adj]) {
continue;
}
unordered_map<int,int> newResults;
for(auto& it : getPathLengths(adj,centroid,k)) {
int weight = it.first + connection.second;
int length = it.second + 1;
if(auxBest[k - weight] == auxCur) {
childMin = min(childMin, allResults[k - weight] + length);
}
newResults[weight] = length;
}
for(auto& it : newResults) {
if(allResults.count(it.first) == 0 || allResults[it.first] > it.second) {
//cout << "added " << it.first << " with " << it.second << " paths" << endl;
allResults[it.first] = it.second;
auxBest[it.first] = auxCur;
}
}
}
for(ii connection : adjList[centroid]) {
int adj = connection.first;
int res = solveFor(adj,centroid);
//cout << "child " << adj << " res " << res << endl;
childMin = min(childMin, res);
}
ign[centroid] = false;
//cerr << "solveFor " << treeStart << " result " << childMin << endl;
return childMin;
}
int best_path(int N, int K, int H[][2], int L[])
{
for(int i = 0; i < N - 1; ++i) {
adjList[H[i][0]].push_back({H[i][1],L[i]});
adjList[H[i][1]].push_back({H[i][0],L[i]});
}
k = K;
int res = solveFor(0,-1);
if(res == 2 * MAXN) {
return -1;
} else {
return res;
}
}
