#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int maxN = 100005;
vector <pair <int, int>> G[maxN];
int dpUp[maxN], dp[maxN], diam[maxN];
pair <int, int> dpDown[maxN], dpDown2[maxN];
bool seen[maxN];
void dfsDown(int nod, int tata) {
for (auto [fiu, cost] : G[nod]) {
if (fiu == tata) {
continue;
}
dfsDown(fiu, nod);
pair <int, int> p = {dpDown[fiu].first + cost, fiu};
if (p > dpDown[nod]) {
dpDown2[nod] = dpDown[nod];
dpDown[nod] = p;
} else if (p > dpDown2[nod]) {
dpDown2[nod] = p;
}
}
}
void dfsUp(int nod, int tata, int cost) {
if (tata != -1) {
dpUp[nod] = dpUp[tata] + cost;
if (dpDown[tata].second == nod) {
dpUp[nod] = max(dpUp[nod], dpDown2[tata].first + cost);
} else {
dpUp[nod] = max(dpUp[nod], dpDown[tata].first + cost);
}
}
for (auto [fiu, cost] : G[nod]) {
if (fiu == tata) {
continue;
}
dfsUp(fiu, nod, cost);
}
}
pair <int, int> dfs(int nod, int tata) {
seen[nod] = 1;
int ans = max(dpDown[nod].first, dpUp[nod]);
int ans2 = ans;
for (auto [fiu, _] : G[nod]) {
if (fiu == tata) {
continue;
}
auto [a, b] = dfs(fiu, nod);
ans = min(ans, a);
ans2 = max(ans2, a);
}
return {ans, ans2};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i++) {
G[A[i]].push_back({B[i], T[i]});
G[B[i]].push_back({A[i], T[i]});
}
int ans = 0;
int cnt = 0;
for (int i = 0; i < N; i++) {
if (seen[i]) {
continue;
}
dfsDown(i, -1);
dfsUp(i, -1, 0);
auto [a, b] = dfs(i, -1);
diam[cnt] = a;
ans = max(ans, b);
cnt++;
}
sort(diam, diam + cnt);
reverse(diam, diam + cnt);
if (cnt == 1) {
return ans;
}
if (cnt == 2) {
return max(ans, diam[0] + diam[1] + L);
}
return max({ans, diam[0] + diam[1] + L, diam[1] + diam[2] + 2 * L});
}
