#include "race.h"
#include <vector>
#include <iostream>
#include <set>
#define ll long long
#define vi vector<int>
#define pii pair<ll, ll>
#define fst first
#define snd second
#define vpi vector<pii>
#define pub push_back
#define spi set<pii>
using namespace std;
const int INF = 1e9;
vpi adj[200001];
int ans = INF, k;
struct DS
{
ll a = 0, b = 0; set<pii> s;
void insert(ll x, ll y) {s.insert({x - a, y - b});}
void offset(ll x, ll y) {a += x; b += y;}
int size() {return s.size();}
int retMin(ll t)
{
auto it = s.upper_bound({t - a, -1000000000});
if (it != s.end() && it -> fst + a == t) return it -> snd + b;
else return INF;
}
};
DS* DFS(int u, int p, int pv)
{
DS* ret = nullptr;
for (auto v : adj[u])
{
if (v.fst != p)
{
DS* ret2 = DFS(v.fst, u, v.snd);
if (ret == nullptr) {ret = ret2;}
else if (ret -> size() < ret2 -> size())
{
for (const auto &v : ret -> s)
{
ll vv = v.fst + ret -> a;
ans = min(ans, (int)ret -> b + (int)v.snd + ret2 -> retMin(k - vv));
}
for (const auto &v : ret -> s)
{
ret2 -> insert(v.fst + ret -> a, v.snd + ret -> b);
}
swap(ret, ret2);
}
else
{
for (const auto &v : ret2 -> s)
{
ll vv = v.fst + ret2 -> a;
ans = min(ans, (int)ret2 -> b + (int)v.snd + ret -> retMin(k - vv));
}
for (const auto &v : ret2 -> s)
{
ret -> insert(v.fst + ret2 -> a, v.snd + ret2 -> b);
}
}
}
}
if (ret == nullptr) {ret = new DS;}
ret -> insert(0, 0);
ans = min(ans, ret -> retMin(k));
/*cout << "Node " << u << " " << p << " " << ret -> a << " " << ret -> b << ":\n";
for (auto x : ret -> s)
{
cout << x.fst + ret -> a << ", " << x.snd + ret -> b << "\n";
}*/
ret -> offset(pv, 1);
return ret;
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for (int i = 0; i < N - 1; i++)
{
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
DFS(0, -1, 0);
if (ans == INF) return -1;
else return ans;
}
