#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; }