// Author: Khulegu Batnasan
// Date: 2023-04-03
#include "race.h"
#include<bits/stdc++.h>
const int MAXN = 1000005;
const int INF = 1000010;
using namespace std;
vector<vector<pair<int, int>>> to;
int n, k;
int ans = INF;
int sz[MAXN];
bool del[MAXN];
// Backlog
map<int, int> dist_min_back;
// <K, V> Save the minimum number of edges with K total length
map<int, int> dist_min;
void calc_size(int u, int pre) {
sz[u] = 1;
for (auto [v, w] : to[u]) {
if (v == pre || del[v]) continue;
calc_size(v, u);
sz[u] += sz[v];
}
}
int find_centroid(int u, int pre, int total) {
for (auto [v, w] : to[u]) {
if (v == pre || del[v]) continue;
if (sz[v] > total / 2) return find_centroid(v, u, total);
}
return u;
}
void collect_distances(int u, int pre, int dist, int edges) {
if (dist_min.count(dist)) {
dist_min[dist] = min(dist_min[dist], edges);
} else {
dist_min[dist] = edges;
}
for (auto [v, w] : to[u]) {
if (v == pre || del[v]) continue;
collect_distances(v, u, dist + w, edges + 1);
}
}
void solve_subtree(int u) {
// Recalculate subtree sizes
calc_size(u, u);
// Find the centroid
int centroid = find_centroid(u, u, sz[u]);
// Mark the centroid as deleted
del[centroid] = true;
dist_min_back.clear();
dist_min_back[0] = 0;
// Decompose
for (auto [v, w] : to[centroid]) {
if (del[v]) continue;
dist_min.clear();
collect_distances(v, centroid, w, 1);
// Calculate the answers with backlog
for (auto [dist, edges] : dist_min) {
if (dist_min_back.count(k - dist)) {
int new_ans = dist_min_back[k - dist] + edges;
ans = min(ans, new_ans);
}
}
// Add to backlog
for (auto [dist, edges] : dist_min) {
if (dist_min_back.count(dist)) {
dist_min_back[dist] = min(dist_min_back[dist], edges);
} else {
dist_min_back[dist] = edges;
}
}
}
// Solve the subtrees
for (auto [v, w] : to[centroid]) {
if (del[v]) continue;
solve_subtree(v);
}
}
int best_path(int _n, int _k, int H[][2], int L[]) {
// Given a tree with N vertices with
// edges H[i][0] and H[i][1] connected
// And edge lengths L[i].
// Find a minimum number of edges with
// their total length equal to exactly K.
// If no such path exists, return -1.
n = _n, k = _k;
to.resize(n);
for (int i = 0; i < n - 1; i++) {
int u = H[i][0], v = H[i][1], w = L[i];
to[u].push_back({v, w});
to[v].push_back({u, w});
}
solve_subtree(0);
return ans == INF ? -1 : ans;
}
