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