#include "race.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define pb push_back
#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;
}
//{length, id}
//save two smalled length, but with different id
set<int> updated;
pair<ii, ii> ar[5 * MAX];
inline pair<ii, ii> combine (pair<ii, ii> _old, ii _new)
{
vector<ii> v;
v.pb(_old.f1);
v.pb(_old.s2);
v.pb(_new);
sort(v.begin(), v.end());
pair<ii, ii> res;
res.f1 = v[0];
if (v[0].s2 != v[1].s2) //different id
res.s2 = v[1];
else res.s2 = v[2];
return res;
}
void dfs(int node, int par, int id, int dist, int h)
{
if (dist > k)
return;
updated.insert(dist);
ar[dist] = combine(ar[dist], {h, id});
for (ii to : adj[node])
{
if (to.f1 != par)
dfs(to.f1, node, id, dist + to.s2, h+1);
}
}
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());
int id = 0;
for (ii e : edge)
dfs(e.f1, c, id++, e.s2, 1);
for (int x : updated)
{
if (ar[x].f1.s2 != ar[k-x].f1.s2)
ans = min(ans, ar[x].f1.f1 + ar[k-x].f1.f1);
else ans = min(ans, ar[x].f1.f1 + ar[k-x].s2.f1);
}
for (int x : updated)
ar[x] = {{inf, inf}, {inf, inf}};
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]});
}
for (int i = 0; i < 5*MAX; ++i)
ar[i] = {{inf, inf}, {inf, inf}};
ans = n;
rc(0);
return ans == n ? -1 : ans;
}
