#include "race.h"
#include "bits/stdc++.h"
using namespace std;
const int sz = 3e5 + 9;
vector< pair<int, int> > v[sz];
map<int, int> mp;
bool used[sz];
int ans = 1e9, k;
int centroidDecomp(int node, int par, int n, int ¢roid)
{
int res = 1;
for (auto to : v[node])
{
if (!used[to.first] && to.first != par)
{
res += centroidDecomp(to.first, node, n, centroid);
}
}
if (centroid == -1 && (par == -1 || ((res << 1) >= n)))
{
centroid = node;
}
return res;
}
void dfs(int node, int par, int dist, int depth, int typ)
{
if (dist == k)
{
ans = min(ans, depth);
return;
}
if (!typ)
{
if (mp.find(k - dist) != mp.end())
{
ans = min(ans, mp[k - dist] + depth);
}
}
else
{
if (mp.find(dist) == mp.end())
{
mp[dist] = depth;
}
mp[dist] = min(mp[dist], depth);
}
for (auto to : v[node])
{
if (!used[to.first] && to.first != par)
{
dfs(to.first, node, dist + to.second, depth + 1, typ);
}
}
}
void calc(int l, int r)
{
int centroid = -1;
centroidDecomp(l, -1, r, centroid);
used[centroid] = 1;
mp.clear();
for (auto x : v[centroid])
{
if (!used[x.first])
{
dfs(x.first, l, x.second, 1, 0);
dfs(x.first, l, x.second, 1, 1);
}
}
for (auto x : v[centroid])
{
if (!used[x.first])
{
calc(x.first, (r >> 1));
}
}
}
int best_path(int n, int K, int h[][2], int l[])
{
for (int i = 0; i < n - 1; ++i)
{
v[h[i][0] + 1].emplace_back(h[i][1] + 1, l[i]);
v[h[i][1] + 1].emplace_back(h[i][0] + 1, l[i]);
}
k = K;
calc(1, n);
return (ans == 1e9 ? -1 : ans);
}
/*
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3 4 5 4 6 3 2 5 6 7
2
*/
