#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);
}
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;
}
int k;
vii pathLengthResults;
int best[1000002];
int auxBest[1000002];
int auxCur = 1;
void getPathLengths(int node, int parent,
int traveled, int steps) {
if(traveled > k) {
return;
}
pathLengthResults.push_back({traveled,steps});
for(ii connection : adjList[node]) {
int adj = connection.first;
int weight = connection.second;
if(adj == parent) {
continue;
}
if(ign[adj]) {
continue;
}
getPathLengths(adj,node, traveled + weight, steps + 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;
int weight,length;
auxBest[0] = auxCur;
for(ii connection : adjList[centroid]) {
int adj = connection.first;
if(ign[adj]) {
continue;
}
pathLengthResults.clear();
getPathLengths(adj,centroid,connection.second,1);
for(ii path : pathLengthResults) {
tie(weight,length) = path;
if(weight < 0 || weight > k) {
continue;
}
if(auxBest[k - weight] == auxCur) {
childMin = min(childMin, best[k - weight] + length);
}
}
for(ii path : pathLengthResults) {
tie(weight,length) = path;
if(auxBest[weight] != auxCur || best[weight] > length) {
//cout << "added " << it.first << " with " << it.second << " paths" << endl;
best[weight] = length;
auxBest[weight] = 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;
}
}
