#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200001;
const int K = 1000001;
vector<array<int, 2>> adj[N];
//int par[N];
int n, k;
bool vis[N];
int dist[K];
int sizOf(int node, int parent)
{
if (vis[node]) return 0;
int res = 1;
for (auto next : adj[node])
{
if (next[0] == parent) continue;
res += sizOf(next[0], node);
}
return res;
}
array<int, 2> dfs2(int node, int par, int siz)
{
if (vis[node]) return {0, -1};
bool good = true;
int down = 0;
for (auto next : adj[node])
{
if (next[0] == par) continue;
auto curr = dfs2(next[0], node, siz);
if (curr[1] != -1) return {-1, curr[1]};
if (curr[0] > siz / 2) good = false;
down += curr[0];
}
good = good && ((siz - down - 1) <= siz / 2);
array<int, 2> res = {down + 1, -1};
if (good) res[1] = node;
return res;
}
int dfs1(int node, int parent, int edges, int cdist, vector<array<int, 2>>& cvis)
{
if (vis[node]) return N;
if (cdist > k) return N;
int res = N;
//cout << node << " a " << cdist << " " << k <<endl;
res = min(res, edges + dist[k - cdist]);
cvis.push_back({cdist, edges});
for (auto next : adj[node])
{
if (next[0] == parent) continue;
res = min(res, dfs1(next[0], node, edges + 1, cdist + next[1], cvis));
}
return res;
}
int solveRoot(int node)
{
if (vis[node]) return N;
int res = N;
vector<int> allVis;
dist[0] = 0;
for (auto next : adj[node])
{
vector<array<int, 2>> cvis;
res = min(res, dfs1(next[0], node, 1, next[1], cvis));
for (auto other : cvis)
{
allVis.push_back(other[0]);
dist[other[0]] = min(dist[other[0]], other[1]);
}
}
for (int other : allVis) dist[other] = N;
//cout << node << " " << res << endl;
//cout << node << " " << res << endl;
return res;
}
int solve(int node)
{
if (vis[node]) return N;
int res = N;
int root = dfs2(node, -1, sizOf(node, -1))[1];
res = min(res, solveRoot(root));
vis[root] = true;
for (auto next : adj[root])
{
//cout << root << " " << next[0] << endl;
res = min(res, solve(next[0]));
}
return res;
}
int best_path(int n1, int k1, int H[][2], int L[])
{
n = n1;
k = k1;
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]});
}
for (int i = 1; i < K; i++) dist[i] = N;
dist[0] = 0;
int res = solve(0);
if (res == N) return -1;
return res;
}
/*
6 200
0 1 25
1 2 35
2 3 40
3 4 50
4 5 50
*/
