#include <bits/stdc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int, int>
using namespace std;
const int N = 2e5 + 5;
const int K = 1e6 + 5;
const int inf = 1e18;
int n, k, ans = inf, sz[N], cal[N];
vector <pii> adj[N], temp;
bool del[N];
void dfssz(int u, int p){
sz[u] = 1;
for (auto [w, v] : adj[u]) {
if (v == p || del[v]) continue;
dfssz(v, u);
sz[u] += sz[v];
}
}
int centroid(int u, int p, int siz){
for (auto [w, v] : adj[u]) {
if (v == p || del[v]) continue;
if (2 * sz[v] > siz) return centroid(v, u, siz);
}
return u;
}
void dfs(int u, int p, int dis, int cnt){
temp.emb(dis, cnt);
if (k >= dis && cal[k - dis] != inf) ans = min(ans, cnt + cal[k - dis]);
for (auto [w, v] : adj[u]) {
if (v == p || del[v]) continue;
dfs(v, u, dis + w, cnt + 1);
}
}
void dfsdel(int u, int p, int dis){
cal[dis] = inf;
for (auto [w, v] : adj[u]) {
if (v == p || del[v]) continue;
dfsdel(v, u, dis + w);
}
}
void decompose(int u){
dfssz(u, u);
u = centroid(u, u, sz[u]);
del[u] = true;
cal[0] = 0;
for (auto [w, v] : adj[u]) {
if (del[v]) continue;
temp.clear();
dfs(v, u, w, 1);
for (auto [dis, cnt] : temp) {
cal[dis] = min(cal[dis], cnt);
}
}
for (auto [w, v] : adj[u]) {
if (del[v]) continue;
dfsdel(v, u, w);
}
for (auto [w, v] : adj[u]) {
if (!del[v]) decompose(v);
}
}
int32_t best_path(int32_t nn, int32_t kk, int32_t edge[][2], int32_t wei[]){
n = nn, k = kk;
for (int i = 0; i <= k; i++) cal[i] = inf;
for (int i = 0; i < n - 1; i++) {
auto v = edge[i];
adj[v[0]].emb(wei[i], v[1]);
adj[v[1]].emb(wei[i], v[0]);
}
decompose(0);
return (ans == inf ? -1 : ans);
}
# | 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... |