#include <bits/stdc++.h>
#include "race.h"
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vii = vector<pii>;
using vll = vector<pll>;
const int maxn = 200000;
const int maxk = 100000;
const int root = 0;
constexpr int INF = 0x3f3f3f3f;
int best_path(int n, int k, int edges[][2], int W[]) {
vector<vii> adj(n);
for (int i = 0; i < n - 1; i++) {
int u = edges[i][0], v = edges[i][1];
adj[u].push_back({v, W[i]});
adj[v].push_back({u, W[i]});
}
vector<pair<ll, int>> dis2root(n), dis2root_order(n);
vi heavy_parent(n, -1), start_time(n), end_time(n), order2node(n);
int timer = 0;
auto dfs = [&](auto &&self, int u, int p) -> void {
start_time[u] = timer;
dis2root_order[timer] = dis2root[u];
order2node[timer] = u;
timer++;
int heavy_child = -1, heavy_size = 0;
for (auto& [v, w]: adj[u]) {
if (v == p) continue;
dis2root[v] = {dis2root[u].F + w, dis2root[u].S + 1};
self(self, v, u);
if (end_time[v] - start_time[v] > heavy_size) {
heavy_size = end_time[v] - start_time[v];
heavy_child = v;
}
}
if (heavy_child != -1) {
heavy_parent[heavy_child] = u;
}
end_time[u] = timer;
};
dfs(dfs, root, -1);
int ans = n;
auto upd = [&](map<ll, int>& mp, const pair<ll, int>& v) {
if (mp.find(v.F) == mp.end()) {
mp[v.F] = v.S;
} else {
mp[v.F] = min(mp[v.F], v.S);
}
};
for (int leaf = 0; leaf < n; leaf++) {
if (end_time[leaf] - start_time[leaf] > 1) continue;
cerr << "leaf: " << leaf << '\n';
map<ll, int> mp; // mp[dis_to_root] = min # of edges
vii todo;
int u = leaf;
upd(mp, dis2root[u]);
while (heavy_parent[u] != -1) {
int p = heavy_parent[u];
cerr << "parent " << p << ' ' << dis2root[p].F << ' ' << dis2root[p].S << '\n';
upd(mp, dis2root[p]);
for (auto& [l, r] : vii{{start_time[p] + 1, start_time[u]}, {end_time[u], end_time[p]}}) {
int subtree = -1;
for (int i = l; i < r; i++) {
cerr << i << '\n';
if (subtree == -1 || i >= end_time[subtree]) {
cerr << "subtree is set to " << order2node[i] << " whose dfs order is " << i << '\n';
subtree = order2node[i];
for (const pii& v: todo) {
upd(mp, v);
}
todo.clear();
}
todo.push_back(dis2root_order[i]);
cerr << "map content\n";
for (auto [key, val]: mp) {
cerr << key << ' ' << val << '\n';
}
if (mp.find(k + 2 * dis2root[p].F - dis2root_order[i].F) != mp.end()) {
ans = min(ans, dis2root_order[i].S + mp[k + 2 * dis2root[p].F - dis2root_order[i].F] - 2 * dis2root[p].S);
}
}
for (const pii& v: todo) {
upd(mp, v);
}
todo.clear();
}
u = p;
}
}
if (ans == n) ans = -1;
return ans;
}
