#include "race.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 200000;
const int MAXK = 1000000;
vector<pair<int, int>> g[MAXN + 1];
int k, viz[MAXN], sz[MAXN], answer, mindepth[MAXK + 1];
void dfsSize(int node, int parent) {
sz[node] = 1;
for(auto edge : g[node]) {
int son = edge.first;
if(son != parent) {
dfsSize(son, node);
sz[node] += sz[son];
}
}
}
int findCentroid(int node, int limit) {
for(auto edge : g[node]) {
int son = edge.first;
if(!viz[son] && sz[son] < sz[node] && sz[son] > limit) {
return findCentroid(son, limit);
}
}
return node;
}
void countPaths(int node, int parent, long long depth_cost, int depth) {
if(depth_cost <= k && mindepth[k - depth_cost] >= 0) {
answer = min(answer, depth + mindepth[k - depth_cost]);
}
for(auto edge : g[node]) {
int son = edge.first, cost = edge.second;
if(!viz[son] && son != parent) {
countPaths(son, node, depth_cost + cost, depth + 1);
}
}
}
void minSelf(int &a, int b) {
if(a > b || a == -1) {
a = b;
}
}
void addPaths(int node, int parent, long long depth_cost, int depth) {
if(depth_cost <= k) {
minSelf(mindepth[depth_cost], depth);
}
for(auto edge : g[node]) {
int son = edge.first, cost = edge.second;
if(!viz[son] && son != parent) {
addPaths(son, node, depth_cost + cost, depth + 1);
}
}
}
void reset(int node, int parent, long long depth_cost) {
if(depth_cost <= k) {
mindepth[depth_cost] = -1;
}
for(auto edge : g[node]) {
int son = edge.first, cost = edge.second;
if(!viz[son] && son != parent) {
reset(son, node, depth_cost + cost);
}
}
}
void checkPaths(int node) {
mindepth[0] = 0;
for(auto edge : g[node]) {
int son = edge.first, cost = edge.second;
if(!viz[son]) {
countPaths(son, node, cost, 1);
addPaths(son, node, cost, 1);
}
}
reset(node, -1, 0);
reverse(g[node].begin(), g[node].end());
mindepth[0] = 0;
for(auto edge : g[node]) {
int son = edge.first, cost = edge.second;
if(!viz[son]) {
countPaths(son, node, cost, 1);
addPaths(son, node, cost, 1);
}
}
reset(node, -1, 0);
}
void decompose(int node) {
dfsSize(node, -1);
node = findCentroid(node, sz[node] / 2);
checkPaths(node);
viz[node] = 1;
for(auto edge : g[node]) {
int son = edge.first;
if(!viz[son]) {
decompose(son);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for(int i = 0; i < N - 1; i++) {
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
k = K;
for(int i = 0; i <= k; i++) {
mindepth[i] = -1;
}
answer = N + 1;
decompose(0);
if(answer == N + 1) {
answer = -1;
}
return answer;
}
