#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define MAXN 200100
#define MAXK 1000100
#define F first
#define S second
int processed[MAXN], size[MAXN], achievable[MAXK], min_paths[MAXK];
vector<pii> neighbours[MAXN];
int bk, ga, split_node, current_max;
void calculate_size(int current, int parent){
::size[current] = 0;
for (int i = 0; i < (int)neighbours[current].size(); i++){
if (!processed[neighbours[current][i].F] && neighbours[current][i].F != parent){
calculate_size(neighbours[current][i].F, current);
::size[current] += 1 + ::size[neighbours[current][i].F];
}
}
}
// we bout to get lit
void select_split_node(int current, int parent, int total){
int n_max = total - ::size[current] - 1;
for (int i = 0; i < (int)neighbours[current].size(); i++){
if (!processed[neighbours[current][i].F] && neighbours[current][i].F != parent){
select_split_node(neighbours[current][i].F, current, total);
n_max = max(n_max, 1 + ::size[neighbours[current][i].F]);
}
}
if (n_max < current_max){
split_node = current;
current_max = n_max;
}
}
void dfs(int current, int parent, int current_cost, int current_length, int fill, int K){
if (current_cost > K){
return;
}
if (!fill){
if (achievable[K - current_cost] == bk){
if (current_length + min_paths[K - current_cost] < ga || ga == -1){
ga = current_length + min_paths[K - current_cost];
}
}
if (current_cost == K){
if (current_length < ga || ga == -1){
ga = current_length;
}
}
}
else {
if (achievable[current_cost] < bk){
achievable[current_cost] = bk;
min_paths[current_cost] = current_length;
}
else if (current_length < min_paths[current_cost]){
achievable[current_cost] = bk;
min_paths[current_cost] = current_length;
}
}
for (int i = 0; i < (int)neighbours[current].size(); i++){
if (!processed[neighbours[current][i].F] && neighbours[current][i].F != parent){
dfs(neighbours[current][i].F, current, current_cost + neighbours[current][i].S, current_length + 1, fill, K); // .S
}
}
}
// final steps
void process(int current, int K){
calculate_size(current, -1);
if (::size[current] <= 1){
return;
}
split_node = -1;
current_max = ::size[current] + 3;
select_split_node(current, -1, ::size[current] + 1);
bk++;
for (int i = 0; i < (int)neighbours[split_node].size(); i++){
if (!processed[neighbours[split_node][i].F]){
dfs(neighbours[split_node][i].F, split_node, neighbours[split_node][i].S, 1, 0, K);
dfs(neighbours[split_node][i].F, split_node, neighbours[split_node][i].S, 1, 1, K);
}
}
int lsn = split_node;
processed[split_node] = 1;
for (int i = 0; i < (int)neighbours[lsn].size(); i++){
if (!processed[neighbours[lsn][i].F]){
process(neighbours[lsn][i].F, K);
}
}
}
// final steps
int best_path(int N, int K, int H[][2], int L[])
{
memset(processed, 0, sizeof(processed));
memset(achievable, 0, sizeof(achievable));
memset(min_paths, 0, sizeof(min_paths));
for (int i = 0; i < N - 1; i++){
neighbours[H[i][0]].push_back({H[i][1], L[i]});
neighbours[H[i][1]].push_back({H[i][0], L[i]}); // i believe??
}
ga = -1;
process(0, K);
return ga;
}
