#include "race.h"
#include <vector>
#include <iostream>
#include <algorithm>
#pragma GCC optimize ("O3")
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 200000;
int const kmax = 1000000;
struct Edge{
int to;
int cost;
};
std::vector<Edge> g[1 + nmax];
int sz[1 + nmax], seen[1 + nmax];
void dfs(int node, int parent){
sz[node] = 1;
for(int h = 0; h < g[node].size(); h++){
Edge e = g[node][h];
if(seen[e.to] == 0 && e.to != parent){
dfs(e.to, node);
sz[node] += sz[e.to];
}
}
}
int find_centroid(int node, int parent, int target){
for(int h = 0; h < g[node].size(); h++){
Edge e = g[node][h];
if(e.to != parent && seen[e.to] == 0 && target < sz[e.to])
return find_centroid(e.to, node, target);
}
return node;
}
int dp[1 + kmax];
void addnode(int node, int parent, int acc, int level, int k){
if(acc <= k)
if(level < dp[acc])
dp[acc] = level;
for(int h = 0; h < g[node].size(); h++){
Edge e = g[node][h];
if(e.to != parent && seen[e.to] == 0)
addnode(e.to, node, acc + e.cost, level + 1, k);
}
}
void deletenode(int node, int parent, int acc, int level, int k){
if(acc <= k)
dp[acc] = nmax;
for(int h = 0; h < g[node].size(); h++){
Edge e = g[node][h];
if(e.to != parent && seen[e.to] == 0)
deletenode(e.to, node, acc + e.cost, level + 1, k);
}
}
void querynode(int node, int parent, int acc, int level, int &result, int k){
if(acc <= k)
if(dp[k - acc] + level < result)
result = dp[k - acc] + level;
for(int h = 0; h < g[node].size(); h++){
Edge e = g[node][h];
if(e.to != parent && seen[e.to] == 0)
querynode(e.to, node, acc + e.cost, level + 1, result, k);
}
}
void solve(int node, int &result, int k){
dp[0] = 0;
dfs(node, -1);
int centroid = find_centroid(node, -1, sz[node] / 2);
for(int h = 0; h < g[centroid].size(); h++){
Edge e = g[centroid][h];
querynode(e.to, centroid, e.cost, 1, result, k);
if(seen[e.to] == 0)
addnode(e.to, centroid, e.cost, 1, k);
}
for(int h = 0; h < g[centroid].size(); h++){
Edge e = g[centroid][h];
if(seen[e.to] == 0)
deletenode(e.to, centroid, e.cost, 1, k);
}
seen[centroid] = 1;
for(int h = 0; h < g[centroid].size(); h++){
Edge e = g[centroid][h];
if(seen[e.to] == 0)
solve(e.to, result, k);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
for(int i = 0; i <= K; i++)
dp[i] = nmax;
for(int i = 0; i < N - 1; i++){
int x = H[i][0], y = H[i][1];
g[x].push_back({y, L[i]});
g[y].push_back({x, L[i]});
}
for(int i = 0; i < N; i++)
std::random_shuffle(g[i].begin(), g[i].end());
int result = nmax;
solve(0, result, K);
//while(1);
if(result < nmax)
return result;
else
return -1;
}
