#include <iostream>
#include <vector>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
using namespace std;
vector<int> subtree_size;
vector<bool> deleted;
// dp[k] := shortest path from y to x of length exactly k in a processed subtree.
unordered_map<int, int> dp;
unordered_map<int, int> local;
struct Graph {
int n;
vector<vector<pair<int, int>>> adj;
int best;
void dfs(int x, int prev) {
// populate subtree sizes
subtree_size.at(x) = 1;
for (auto& p : adj.at(x)) {
int y = p.first;
if (y == prev) continue;
if (deleted.at(y)) continue;
dfs(y, x);
subtree_size.at(x) += subtree_size.at(y);
}
}
int dfs2(int x, int prev) {
// return the centroid
for (auto& p : adj[x]) {
int y = p.first;
if (y == prev) continue;
if (deleted[y]) continue;
if (subtree_size[x] / 2 < subtree_size[y]) {
return dfs2(y, x);
}
}
return x;
}
int find_centroid(int x) {
// starting from x, find the centroid of g
// find the size of all subtrees.
dfs(x, -1);
// find the centroid using subtree_size
return dfs2(x, -1);
}
};
void dfs3(int x, int prev, int d, int depth, int k, Graph& g) {
// d is already greater than k, can stop here.
if (k < d) {
return;
}
// d is exactly k:
if (k == d) {
g.best = min(g.best, depth);
return;
}
// 1. update local
if (dp.count(d) > 0 && dp[d] < depth) {
// skip
}
else if (local.count(d) == 0) {
local[d] = depth;
}
else {
local[d] = min(local[d], depth);
}
// 2. check if there is a path of length k using this node to centroid to another subtree.
if (dp.count(k-d) > 0) {
g.best = min(depth + dp[k-d], g.best);
}
// iterate over each subtree
for (auto& p : g.adj[x]) {
int y = p.first;
int dist = p.second;
if (y == prev) continue;
if (deleted[y]) continue;
dfs3(y, x, d+dist, depth+1, k, g);
}
}
void rec(int x, int k, Graph& g) {
// find all paths of length k that run through x.
// cout << "Using centroid = " << x << endl;
dp.clear();
local.clear();
// iterate over each subtree and compute paths.
for (auto& p : g.adj[x]) {
int y = p.first;
int d = p.second;
if (deleted[y]) continue;
dfs3(y, x, d, 1, k, g);
// update dp with local
for (auto& localp : local) {
int a = localp.first;
int b = localp.second;
if (dp.count(a) == 0) {
dp[a] = b;
}
else {
dp[a] = min(dp[a], b);
}
}
// // print dp
// cout << "After y: " << y << endl;
// for (auto& localp : dp) {
// int a = localp.first;
// int b = localp.second;
// cout << "dp[" << a << "] = " << b << endl;
// }
// cout << "Min = " << g.best << endl;
}
// delete x
deleted[x] = true;
// iterate over each subtree and recurse.
for (auto& p : g.adj[x]) {
int y = p.first;
if (deleted[y]) continue;
y = g.find_centroid(y);
rec(y, k, g);
}
}
int best_path(int n, int k, int h[][2], int l[]) {
// Set up adjacency matrix
Graph g;
g.n = n;
g.adj.resize(n);
g.best = 1000001;
deleted.resize(n);
subtree_size.resize(n);
for (int i = 0; i < n-1; i++) {
int x = h[i][0];
int y = h[i][1];
int d = l[i];
g.adj[x].emplace_back(y, d);
g.adj[y].emplace_back(x, d);
}
// // print the graph g:
// for (int i = 0; i < n; i++) {
// cout << "i = " << i << endl;
// for (int j = 0; j < g.adj[i].size(); j++) {
// cout << g.adj[i][j].first << " " << g.adj[i][j].second << endl;
// }
// }
// centroid decomposition
int c = g.find_centroid(0);
rec(c, k, g);
if (g.best > 1000000) {
return -1;
}
return g.best;
}
// Parse input:
// int N, K;
// int H[200005][2];
// int L[200005];
// int main () {
// ios::sync_with_stdio(false);
// cin >> N >> K;
// for (int i = 0; i < N-1; i++) {
// cin >> H[i][0] >> H[i][1] >> L[i];
// }
// cout << best_path(N, K, H, L) << endl;
// }
