#include "race.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXNUM = 1000000 + 10;
const int INF = 1e9;
int n, k;
int sz[MAXN];
bool vis[MAXN];
int level[MAXN];
int cnt[MAXNUM];
std::vector <std::pair <int,int>> g[MAXN];
std::vector <int> decomp[MAXN];
void calcSize(int node, int par)
{
sz[node] = 1;
for (const auto &[u, cost] : g[node])
{
if (u == par || vis[u])
{
continue;
}
calcSize(u, node);
sz[node] += sz[u];
}
}
int findCentroid(int node, int par, int size)
{
for (const auto &[u, cost] : g[node])
{
if (u == par || vis[u])
{
continue;
}
if (sz[u] > size / 2)
{
return findCentroid(u, node, size);
}
}
return node;
}
int decompose(int node, int par)
{
calcSize(node, 0);
int cntr = findCentroid(node, par, sz[node]);
decomp[par].push_back(cntr);
level[cntr] = level[par] + 1;
vis[cntr] = true;
for (const auto &[u, cost] : g[cntr])
{
if (vis[u])
{
continue;
}
decompose(u, cntr);
}
return cntr;
}
int updateDFS(int node, int par, int sum, int lvl)
{
if (sum > k)
{
return INF;
}
int res = cnt[k - sum];
for (const auto &[u, cost] : g[node])
{
if (level[u] <= lvl || u == par)
{
continue;
}
res = std::min(res, updateDFS(u, node, sum + cost, lvl) + 1);
}
return res;
}
void addDFS(int node, int par, int sum, int edges, int lvl)
{
if (sum > k)
{
return;
}
cnt[sum] = std::min(cnt[sum], edges);
for (const auto &[u, cost] : g[node])
{
if (level[u] <= lvl || u == par)
{
continue;
}
addDFS(u, node, sum + cost, edges + 1, lvl);
}
}
void clearDFS(int node, int par, int sum, int edges, int lvl)
{
if (sum > k)
{
return;
}
cnt[sum] = INF;
for (const auto &[u, cost] : g[node])
{
if (level[u] <= lvl || u == par)
{
continue;
}
clearDFS(u, node, sum + cost, edges + 1, lvl);
}
}
int rec(int node)
{
int ans = INF;
for (const int &u : decomp[node])
{
ans = std::min(ans, rec(u));
}
cnt[0] = 0;
for (const auto &[u, cost] : g[node])
{
if (level[u] > level[node])
{
ans = std::min(ans, 1 + updateDFS(u, node, cost, level[node]));
addDFS(u, node, cost, 1, level[node]);
}
}
for (const auto &[u, cost] : g[node])
{
if (level[u] > level[node])
{
clearDFS(u, node, cost, 1, level[node]);
}
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
std::fill(cnt + 1, cnt + 1 + k, INF);
for (int i = 0 ; i < n - 1 ; ++i)
{
g[H[i][0] + 1].push_back({H[i][1] + 1, L[i]});
g[H[i][1] + 1].push_back({H[i][0] + 1, L[i]});
}
int root = decompose(1, 0);
int res = rec(root);
if (res == INF) return -1;
return res;
}
