#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int N = 2e5 + 10;
bool vis[N];
int sz[N], k;
map<ll, int> mn;
ll ans = LLONG_MAX;
vector<pair<int, ll>> G[N];
int dfsSZ(int node, int par = -1)
{
sz[node] = 1;
for(auto &[ch, w]: G[node])
{
if(ch == par || vis[node])
continue;
sz[node] += dfsSZ(ch, node);
}
return sz[node];
}
int getCentroid(int node, int par, int &n)
{
for(auto &[ch, w]: G[node])
{
if(ch == par || vis[ch])
continue;
if(sz[ch] << 1 > n)
return getCentroid(ch, node, n);
}
return node;
}
void dfs(int node, int par, int dist, int dep)
{
if(mn.count(dist))
mn[dist] = min(mn[dist], dep);
else
mn[dist] = dep;
for(auto &[ch, w]: G[node])
{
if(ch == par || vis[ch])
continue;
dfs(ch, node, dist + w, dep + 1);
}
}
ll solve(int node, int par, int dist, int dep)
{
if(dist > k)
return LLONG_MAX;
ll ret = LLONG_MAX;
if(mn.count(k - dist) && mn[k - dist])
ret = mn[k - dist] + dep;
for(auto &[ch, w]: G[node])
{
if(ch == par || vis[ch])
continue;
ret = min(ret, solve(ch, node, dist + w, dep + 1));
}
return ret;
}
void solveSubTree(int centroid, int par, int d)
{
for(auto &[ch, w]: G[centroid])
{
if(ch == par || vis[ch])
continue;
ans = min(ans, solve(ch, centroid, d + w, 1));
dfs(ch, centroid, d + w, 1);
}
mn.clear();
}
void decompose(int node, int par, int d)
{
dfsSZ(node, par);
int centroid = getCentroid(node, par, sz[node]);
vis[centroid] = true;
solveSubTree(centroid, par, d);
for(auto &[ch, w]: G[centroid])
{
if(ch == par || vis[ch])
continue;
decompose(ch, centroid, d + w);
}
}
int best_path(int n, int K, int H[][2], int L[])
{
k = K;
for(int i = 0; i < n - 1; i++)
{
G[H[i][0]].emplace_back(H[i][1], L[i]);
G[H[i][1]].emplace_back(H[i][0], L[i]);
}
decompose(1, -1, 0);
if(ans == LLONG_MAX)
return -1;
else
return ans;
}
