#include "dreaming.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pr = pair<int, int>; #define pb push_back const int INF = 1e9+7; vector<vector<pr>> edge; vector<int> dp, maxd; int res = 0, curm; int dfs1(int node, int par) { int ans = 0; for (auto [next, val] : edge[node]) { if (next == par) continue; int t = dfs1(next, node); res = max(res, t + ans + val); ans = max(ans, t + val); } return dp[node] = ans; } void dfs2(int node, int par, int parv) { int sz = edge[node].size(); int ans = parv; vector<int> pref(sz+1, 0), suff(sz+2, 0); for (int i = 0; i < sz; i++) { if (edge[node][i].first == par) pref[i+1] = pref[i]; else pref[i+1] = max(pref[i], dp[edge[node][i].first] + edge[node][i].second); } for (int i = sz-1; i >= 0; i--) { if (edge[node][i].first == par) suff[i+1] = suff[i+2]; else suff[i+1] = max(suff[i+2], dp[edge[node][i].first] + edge[node][i].second); } ans = max(ans, pref[sz]); for (int i = 0; i < sz; i++) { if (edge[node][i].first == par) continue; dfs2(edge[node][i].first, node, max({parv, pref[i], suff[i+2]}) + edge[node][i].second); } curm = min(curm, max(parv, pref[sz])); return; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { edge.resize(N); dp.assign(N, -1); maxd.assign(N, -1); for (int i = 0; i < M; i++) { edge[A[i]].pb({B[i], T[i]}); edge[B[i]].pb({A[i], T[i]}); } int mx = 0; vector<int> part; for (int i = 0; i < N; i++) { if (dp[i] == -1) { curm = INF; dfs1(i, -1); int t = curm; part.pb(t); } } sort(part.rbegin(), part.rend()); if (part.size() > 1) res = max(res, part[0] + part[1] + L); if (part.size() > 2) res = max(res, part[1] + part[2] + L + L); return res; }