#include "race.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define ii pair<int, int>
#define f1 first
#define s2 second
const int MAX = 2e5 + 7;
const int inf = 1e9 + 7;
int n, k;
int sz[MAX];
set<ii> adj[MAX];
static int ans;
int get_sz(int node, int par)
{
sz[node] = 1;
for (ii to : adj[node])
if (to.f1 != par)
sz[node] += get_sz(to.f1, node);
return sz[node];
}
int centroid(int node, int par, int n)
{
for (ii to : adj[node])
if (to.f1 != par && sz[to.f1] > n/2)
return centroid(to.f1, node, n);
return node;
}
//{distance, length, id
vector<pair<int, ii>> vec;
void dfs(int node, int par, int id, int dist, int h, bool zero)
{
if (dist > k)
return;
if (!zero) //prevent duplicate data
vec.pb({dist, {h, id}});
for (ii to : adj[node])
{
if (to.f1 != par)
dfs(to.f1, node, id, dist + to.s2, h+1, to.s2 == 0);
}
}
void rc(int node)
{
int n = get_sz(node, -1);
int c = centroid(node, -1, n);
vector<ii> edge(adj[c].begin(), adj[c].end());
vec.clear();
vec.pb({0, {0, 0}});
int id = 1;
for (ii e : edge)
dfs(e.f1, c, id++, e.s2, 1, false);
sort(vec.begin(), vec.end());
{
vector<pair<int, ii>> nv;
nv.pb(vec[0]);
set<ii> inserted; //distance, id
for (int i = 1; i < vec.size(); ++i)
{
if (!inserted.count({vec[i].f1, vec[i].s2.s2}))
{
inserted.insert({vec[i].f1, vec[i].s2.s2});
nv.pb(vec[i]);
}
}
vec = nv;
}
for (pair<int, ii> x : vec)
{
auto it = lower_bound(vec.begin(), vec.end(), mp(k - x.f1, mp(-1, -1)));
if (it == vec.end())
continue;
if ((*it).s2.s2 == x.s2.s2)
it = next(it);
if (it == vec.end())
continue;
if ((*it).f1 != k - x.f1)
continue;
assert((*it).s2.s2 != x.s2.s2);
ans = min(ans, (*it).s2.f1 + x.s2.f1);
}
for (ii e : edge)
{
adj[c].erase(e);
adj[e.f1].erase({c, e.s2});
rc(e.f1);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N, k = K;
for (int i = 0; i < N-1; ++i)
{
adj[H[i][0]].insert({H[i][1], L[i]});
adj[H[i][1]].insert({H[i][0], L[i]});
}
ans = n;
rc(0);
return ans == n ? -1 : ans;
}
