#include <bits/stdc++.h>
#define alle(Lotus) Lotus.begin(), Lotus.end()
using namespace std;
typedef long long ll;
const int maxn = 200005;
int n;
ll k;
const int INF = 1e9 + 7;
int ans = INF;
vector<int> sz(maxn, 1), bigchild(maxn, -1), dep(maxn, 0);
vector<ll> dist(maxn, 0);
vector<int> adj[maxn];
map<pair<int, int>, ll> wei;
map<ll, int> mp;
void pre_dfs(int a, int par) {
for (auto &elm : adj[a]) {
if (elm == par) continue;
dep[elm] = dep[a] + 1;
dist[elm] = dist[a] + wei[{a, elm}];
pre_dfs(elm, a);
sz[a] += sz[elm];
if (bigchild[a] == -1 || sz[bigchild[a]] < sz[elm])
bigchild[a] = elm;
}
}
void add(int a, int par, bool godown, ll distlca, int deplca) {
ll dist1 = k + 2 * distlca - dist[a];
if (dist1 >= 0) {
auto it = mp.find(dist1);
if (it != mp.end()) {
ans = min(ans, it->second + dep[a] - 2 * deplca);
}
}
auto it2 = mp.find(dist[a]);
if (it2 == mp.end()) {
mp[dist[a]] = dep[a];
} else {
mp[dist[a]] = min(mp[dist[a]], dep[a]);
}
if (!godown) return;
for (auto &elm : adj[a]) {
if (elm == par) continue;
add(elm, a, true, distlca, deplca);
}
}
void dfs(int a, int par, bool keep) {
for (auto &elm : adj[a]) {
if (elm == par || elm == bigchild[a]) continue;
dfs(elm, a, false);
}
if (bigchild[a] != -1) {
dfs(bigchild[a], a, true);
}
add(a, par, false, dist[a], dep[a]);
for (auto &elm : adj[a]) {
if (elm == par || elm == bigchild[a]) continue;
add(elm, a, true, dist[a], dep[a]);
}
if (!keep) {
mp.clear();
}
}
signed best_path(signed N, signed K, signed H[][2], signed L[]) {
n = N;
k = (ll)K;
ans = INF;
wei.clear();
mp.clear();
for (int i = 0; i < maxn; ++i) {
adj[i].clear();
sz[i] = 1;
bigchild[i] = -1;
dep[i] = 0;
dist[i] = 0;
}
for (int i = 0; i < n - 1; ++i) {
int x = H[i][0], y = H[i][1];
ll w = L[i];
adj[x].push_back(y);
adj[y].push_back(x);
wei[{x, y}] = w;
wei[{y, x}] = w;
}
pre_dfs(0, -1);
dfs(0, -1, true);
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... |