#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5 + 5, MAXK = 1e6 + 5;
long long knapsack[MAXK];
vector<pair<long long, long long> > g[MAXN];
bool vis[MAXN];
long long subtree[MAXN], ans, k;
vector<long long> changes;
long long Dfs(long long node, long long par = -1) {
subtree[node] = 1;
for(long long i = 0; i < g[node].size(); i++) {
if(!vis[g[node][i].first] && g[node][i].first != par) {
subtree[node] += Dfs(g[node][i].first, node);
}
}
return subtree[node];
}
long long FindCentroid(long long node, long long subtreeSize, long long par = -1) {
for(long long i = 0; i < g[node].size(); i++) {
if(!vis[g[node][i].first] && g[node][i].first != par) {
if(subtree[g[node][i].first] > subtreeSize / 2) {
return FindCentroid(g[node][i].first, subtreeSize, node);
}
}
}
return node;
}
void DfsSubtree(long long node, long long par, long long cur_len, long long cur_roads, bool taking) {
if(cur_len > k) {
return;
}
if(taking) {
//cout << "node = " << node << ", par = " << par << ", cur_len = " << cur_len << ", cur_roads = " << cur_roads << ", values = " << knapsack[k - cur_len] + cur_roads << "\n";
//cout << "Node = " << node << ", ans = " << ans << "\n";
ans = min(ans, knapsack[k - cur_len] + cur_roads);
//cout << "Node = " << node << ", ans = " << ans << "\n";
}
else {
if(knapsack[cur_len] > cur_roads) {
knapsack[cur_len] = cur_roads;
changes.push_back(cur_len);
}
}
for(long long i = 0; i < g[node].size(); i++) {
if(vis[g[node][i].first] || g[node][i].first == par) {
continue;
}
DfsSubtree(g[node][i].first, node, cur_len + g[node][i].second, cur_roads + 1, taking);
}
//cout << "node = " << node << ", ans = " << ans << "\n";
}
void DecomposeTree(long long node) {
long long subtreeSize = Dfs(node);
long long cur_centroid = FindCentroid(node, subtreeSize);
//cout << "cur_centroid = " << cur_centroid << "\n"; //is perfect
vis[cur_centroid] = true;
for(int i = 0; i < g[cur_centroid].size(); i++) {
if(!vis[g[cur_centroid][i].first]) {
DfsSubtree(g[cur_centroid][i].first, cur_centroid, g[cur_centroid][i].second, 1LL, true); //first take all, then fill, to ensure nothing from same subtree is taken
DfsSubtree(g[cur_centroid][i].first, cur_centroid, g[cur_centroid][i].second, 1LL, false);
}
}
for(long long i = 0; i < changes.size(); i++) {
knapsack[changes[i]] = 1e15;
}
changes.clear();
for(long long i = 0; i < g[cur_centroid].size(); i++) {
if(!vis[g[cur_centroid][i].first]) {
DecomposeTree(g[cur_centroid][i].first);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
ans = 1e15;
k = K;
for(long long i = 0; i < N - 1; i++) {
g[H[i][0]].push_back(make_pair(H[i][1], L[i]));
g[H[i][1]].push_back(make_pair(H[i][0], L[i]));
}
for(long long i = 1; i <= k; i++) {
knapsack[i] = 1e15;
}
DecomposeTree(0);
if(ans == 1e15) return -1;
return ans;
}
