#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define x first
#define y second
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define MP make_pair
typedef long long ll;
typedef double db;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<db, db> pdd;
typedef pair<ll, ll> pll;
typedef vector<int> VI;
typedef vector<ll> VL;
const int INF = 1e9 + 47;
const int MAXN = 2e5 + 47;
const int LOG = 17;
vector<pii> g[MAXN];
int siz[MAXN];
bool usedC[MAXN];
vector<array<ll, 3>> ancestors[MAXN];
vector<bool> isLeaf;
ll dist[MAXN];
int distPath[MAXN];
struct SparseTable
{
VI t[LOG];
void push_back(int v)
{
int i = sz(t[0]);
t[0].pb(v);
FOR (j, 0, LOG - 1)
t[j + 1].pb(min(t[j][i], t[j][max(0, i - (1 << j))]));
}
// [l, r)
int query(int l, int r)
{
assert(l < r && r <= sz(t[0]));
int i = 31 - __builtin_clz(r - l);
return min(t[i][r - 1], t[i][l + (1 << i) - 1]);
}
};
struct LCA
{
int n;
VI I; // v -> po(v)
VI RI;
VI M; // to index mapping
VI D;
SparseTable st;
LCA(int _n, int root)
{
n = _n;
I = VI(n);
RI = VI(n);
D = VI(n, -1);
M = VI(2 * n, -1);
int ctr = 0;
vector<int> a;
function<void(int, int, int)> preorder = [&](int v, int pr, int d)
{
I[v] = ctr++;
RI[I[v]] = v;
a.pb(I[v]);
D[v] = d;
for(auto [to, w]: g[v])
{
if(to != pr)
{
preorder(to, v, d + 1);
a.pb(I[v]);
}
}
};
preorder(root, -1, 0);
FOR(i, 0, sz(a)) st.pb(a[i]);
FOR(i, 0, sz(a)) M[a[i]] = i;
}
int lca(int u, int v)
{
return RI[st.query(min(M[I[u]], M[I[v]]), max(M[I[u]], M[I[v]]) + 1)];
}
};
void dfs1(int v, int par, ll d, int path)
{
dist[v] = d;
distPath[v] = path;
for (const auto& [to, w]: g[v])
{
if (to == par)
continue;
dfs1(to, v, d + w, path + 1);
}
}
int dfsSZ(int v, int par)
{
siz[v] = 1;
for (auto [to, w] : g[v])
{
if (to != par && !usedC[to])
siz[v] += dfsSZ(to, v);
}
return siz[v];
}
void dfsDist(int v, int par, int cent, ll d, int path)
{
if (path)
isLeaf[cent] = false;
ancestors[v].pb({cent, d, path});
for (const auto& [to, w]: g[v])
{
if (to == par || usedC[to])
continue;
dfsDist(to, v, cent, d + w, path + 1);
}
}
void build(int u)
{
dfsSZ(u, -1);
int szAll = siz[u];
int pr = u;
while (true)
{
int v = -1;
for (auto [to, w] : g[u])
{
if (to == pr || usedC[to])
continue;
if (siz[to] * 2 > szAll)
{
v = to;
break;
}
}
if (v == -1)
break;
pr = u;
u = v;
}
int cent = u;
usedC[cent] = true;
dfsDist(cent, -1, cent, 0, 0);
for (auto [to, w] : g[cent])
{
if (!usedC[to])
{
build(to);
}
}
}
int best_path(int N, int K_, int H[][2], int L[])
{
int n = N, k = K_;
FOR (i, 0, n - 1)
{
int a = H[i][0], b = H[i][1], d = L[i];
g[a].pb({b, d});
g[b].pb({a, d});
}
dfs1(0, -1, 0, 0);
LCA lca(n, 0);
isLeaf.assign(n, true);
vector<map<ll, multiset<int>>> mp(n);
FOR (v, 0, n)
{
for (const auto& [cent, d, path]: ancestors[v])
{
mp[cent][d].insert(path);
}
}
int ans = INF;
FOR (st, 0, n)
{
if (!isLeaf[st])
continue;
sort(all(ancestors[st]), [](const array<ll, 3>& l, const array<ll, 3>& r) -> bool
{
assert(l[2] != r[2]);
return l[2] < r[2];
});
VI vec;
vector<array<ll, 3>> toAdd;
for (const auto& [cent, d, path]: ancestors[st])
{
vec.pb(cent);
for (int el: vec)
{
// erase el contribtuion from cent
int lc = lca.lca(cent, el);
ll dd = dist[cent] + dist[el] - 2 * dist[lc];
int pp = distPath[cent] + distPath[el] - 2 * distPath[lc];
toAdd.pb({cent, dd, pp});
assert(mp[cent][dd].count(pp));
mp[cent][dd].erase(pp);
}
if (mp[cent].count(k - d) && !mp[cent][k - d].empty())
ans = min(ans, *(mp[cent][k - d].begin()) + (int)path);
}
for (const auto& [cent, dd, pp]: toAdd)
mp[cent][dd].insert(pp);
}
if (ans == INF)
ans = -1;
return ans;
}
