#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int findCentroid(vector<vector<pair<int, int>>> &adjacency, vector<bool> &erased, int cur, int parent, int sz, int &found) {
bool isCentroid = true;
int curCount = 1;
for (auto &[i, j] : adjacency[cur]) {
if (i == parent || erased[i]) continue;
int d = findCentroid(adjacency, erased, i, cur, sz, found);
if (found) return d;
if (sz < 2 * d) isCentroid = false;
curCount += d;
}
if (sz > 2 * curCount) isCentroid = false;
if (isCentroid) {
found = 1;
return cur;
}
return curCount;
}
void findPathsLengths(vector<vector<pair<int, int>>> &adjacency, vector<unordered_map<int, int>> &maps, vector<bool> &erased, int cur, int parent, int shift) {
maps[cur][shift] = 1;
for (auto &[child, length] : adjacency[cur]) {
if (child == parent || erased[child]) continue;
findPathsLengths(adjacency, maps, erased, child, cur, shift);
for (auto &[i, j] : maps[child]) {
if (maps[cur].count(i + length)) maps[cur][i + length] = min(maps[cur][i + length], j + 1);
else maps[cur][i + length] = j + 1;
}
}
}
void recurseForSubTree(int N, int K, vector<vector<pair<int, int>>> &adjacency, vector<unordered_map<int, int>> &maps, vector<bool> &erased, int &res, int cur, int sz) {
int found = 0;
int centroid = findCentroid(adjacency, erased, cur, -1, sz, found);
// cout << "CURRENT CENTROID: " << centroid << " IN TREE WITH SIZE: " << sz << " AND RES BEFORE: " << res << endl;
erased[centroid] = true;
if (sz == 1) return;
maps[centroid][0] = 0;
for (auto &[child, length] : adjacency[centroid]) {
if (erased[child]) continue;
findPathsLengths(adjacency, maps, erased, child, -1, length);
for (auto &[i, j] : maps[child]) {
if (maps[centroid].count(K - i)) res = min(res, j + maps[centroid][K - i]);
}
for (auto &[i, j] : maps[child]) {
if (maps[centroid].count(i)) maps[centroid][i] = min(maps[centroid][i], j);
else maps[centroid][i] = j;
}
}
// cout << "CENTROID: " << centroid << " COMPLETE WITH RES: " << res << endl;
}
void dfs(int cur, int parent, vector<bool> &visited, vector<bool> &erased, vector<vector<pair<int, int>>> &adjacency, int &cnt) {
++cnt;
visited[cur] = true;
for (auto &[i, j] : adjacency[cur]) {
if (i == parent || erased[i]) continue;
dfs(i, cur, visited, erased, adjacency, cnt);
}
}
bool recurseAllSubtrees(int N, int K, vector<vector<pair<int, int>>> &adjacency, vector<unordered_map<int, int>> &maps, vector<bool> &erased, int &res) {
for (auto &i : maps) i.clear();
bool done = true;
vector<bool> visited(N, false);
for (int i = 0; i < N; ++i) {
if (visited[i] || erased[i]) continue;
int cnt = 0;
dfs(i, -1, visited, erased, adjacency, cnt);
recurseForSubTree(N, K, adjacency, maps, erased, res, i, cnt);
done = false;
}
// cout << "LOOP COMPLETE WITH RES: " << res << ". " << (done ? "ALL COMPLETE. " : "MODIFICATIONS DONE. ") << endl;
return done;
}
int best_path(int N, int K, int H[][2], int L[])
{
vector<vector<pair<int, int>>> adjacency(N);
for (int i = 0; i < N - 1; ++i) {
adjacency[H[i][0]].emplace_back(H[i][1], L[i]);
adjacency[H[i][1]].emplace_back(H[i][0], L[i]);
}
vector<unordered_map<int, int>> maps(N);
vector<bool> erased(N, false);
int res = 1e9;
while (!recurseAllSubtrees(N, K, adjacency, maps, erased, res)) continue;
return (res < 1e9 ? res : -1);
}
