#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 200001
typedef vector<vector<pair<int,int>>> adjList;
adjList adj;
vector<int> sizes;
int update_sizes(int n, int p){
sizes[n] = 1;
for(auto[a,x] : adj[n]){
if(a == p) continue;
sizes[n] += update_sizes(a, n);
}
return sizes[n];
}
int find_centroid(int n, int p, int S){
for(auto[a,x] : adj[n]){
if(a == p) continue;
if(sizes[a] > S/2) return find_centroid(a, n, S);
}
return n;
}
// current node, parent, used lenght, used nodes
void find_vals(int n, int p, int l, int c, map<int,int> &r){
if(r.find(l) == r.end()) r[l] = c;
r[l] = min(r[l], c);
for(auto[a,x] : adj[n]){
if(a == p) continue;
find_vals(a, n, l+x, c+1, r);
}
}
int K;
int generate_size_path(int n){
update_sizes(n, -1);
int c = find_centroid(n, -1, sizes[n]);
map<int,int> best_solutions;
best_solutions[0] = 0;
int best = INF;
for(auto[a,ax] : adj[c]){
// Find cost for path of varius lenght and merge
map<int,int> vals;
find_vals(a, c, ax, 1, vals);
for(auto[x,l] : vals){
// se questo percorso è lungo x, l'altro è lungo K-x
if(best_solutions.find(K-x) != best_solutions.end()){
best = min(best, l+best_solutions[K-x]);
}
}
for(auto[x,l] : vals){
if(best_solutions.find(x) == best_solutions.end()) best_solutions[x] = l;
best_solutions[x] = min(best_solutions[x], l);
}
}
cerr << best << endl;
// devo togliere gli archi di c e ricorrere sui sottoarchi
while(!adj[c].empty()){
auto[a,x] = *adj[c].begin();
auto it = adj[a].begin();
while(it->first != c) it++;
adj[a].erase(it);
adj[c].erase(adj[c].begin());
}
return best;
}
// K è la lunghezza
int best_path(int N, int _K, int H[][2], int L[]){
adj.resize(N);
sizes.resize(N);
K =_K;
for(int i = 0 ; i < N-1; i++){
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
return generate_size_path(0);
}
