#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 6;
int best_path(int N, int K, int H[][2], int L[]) {
vector<array<int, 2>> g[N];
for (int i = 0;i < N - 1;i ++) {
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
int res = 1e9 + 7, mx = 0;
vector<int> used(N, 0), sub(N, 0), dist(MAXN, 0);
function<void(int, int)> dfs_init = [&](int si, int pi) -> void {
sub[si] = 1;
for (auto [ti, wi] : g[si]) if (ti != pi && used[ti] == 0) {
dfs_init(ti, si);
sub[si] += sub[ti];
}
};
function<int(int, int, int)> get_centr = [&](int si, int pi, int sz) -> int {
for (auto [ti, wi] : g[si]) if (used[ti] == 0 && ti != pi && sub[ti] * 2 >= sz) {
return get_centr(ti, si, sz);
}
return si;
};
function<void(int, int, int, int)> calc = [&](int si, int pi, int depth, int len) -> void {
if (len > K) return;
if (len == K) res = min(res, depth);
mx = max(mx, len);
if (dist[K - len] != 0) res = min(res, dist[K - len] + depth);
for (auto [ti, wi] : g[si]) if (ti != pi && used[ti] == 0) {
calc(ti, si, depth + 1, len + wi);
}
};
function<void(int, int, int, int)> update = [&](int si, int pi, int depth, int len) -> void {
if (len > K) return;
if (dist[len] == 0) dist[len] = depth;
else dist[len] = min(dist[len], depth);
for (auto [ti, wi] : g[si]) if (ti != pi && used[ti] == 0) {
update(ti, si, depth + 1, len + wi);
}
};
function<void(int)> decompose = [&](int si) -> void {
dfs_init(si, si);
if (sub[si] == 1) return;
int centr = get_centr(si, si, sub[si]);
used[centr] = 1;
mx = 0;
for (auto [ti, wi] : g[centr]) if (used[ti] == 0) {
calc(ti, centr, 1, wi);
update(ti, centr, 1, wi);
}
for (int i = 0;i <= mx;i ++) dist[i] = 0;
for (auto [ti, wi] : g[centr]) if (used[ti] == 0) {
decompose(ti);
}
};
decompose(0);
if (res == 1e9 + 7) return -1;
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |