#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int>>> g;
vector<bool> seen;
// +++ FINDS DIAMETER OF COMPONENT GIVEN ANY NODE +++
pair<int, int> findFurthest(int v, int parent = -1) { // returns distance, node
seen[v] = true;
pair<int, int> furthest{0, v};
for (pair<int, int> u : g[v]) {
if (u.first == parent) continue;
pair<int, int> d = findFurthest(u.first, v);
d.first += u.second;
if (d > furthest) furthest = d;
}
return furthest;
}
int diameter(int v) {
pair<int, int> furthest = findFurthest(v);
return findFurthest(furthest.second).first;
}
// ------------------ END DIAMETER ------------------
vector<int> longest, longestID, secondLongest; // with first move down
int dfs1(int v, int parent = -1) {
seen[v] = true;
for (pair<int, int> u : g[v]) {
if (u.first == parent) continue;
int d = u.second + dfs1(u.first, v);
if (d >= longest[v]) {
secondLongest[v] = longest[v];
longest[v] = d, longestID[v] = u.first;
} else if (d > secondLongest[v]) secondLongest[v] = d;
}
return longest[v];
}
vector<int> longestFrom;
int dfs2(int v, int bestUp = 0, int parent = -1) {
seen[v] = true;
longestFrom[v] = max(longest[v], bestUp);
int minLongest = longestFrom[v];
for (pair<int, int> u : g[v]) {
if (u.first == parent) continue;
int child;
if (u.first == longestID[v]) {
child = dfs2(u.first, u.second + max(secondLongest[v], bestUp), v);
} else {
child = dfs2(u.first, u.second + max(longest[v], bestUp), v);
}
minLongest = min(minLongest, child);
}
return minLongest;
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
g.resize(n);
for (int i = 0; i < m; ++i) {
g[A[i]].emplace_back(B[i], T[i]);
g[B[i]].emplace_back(A[i], T[i]);
}
// find longest distance from each node
longest.resize(n), longestID.resize(n, -1), secondLongest.resize(n);
seen.resize(n);
for (int i = 0; i < n; ++i) {
if (!seen[i]) dfs1(i);
}
// finish finding longest distances
// and find smallest longest distance in each component
vector<int> vals; // gates
longestFrom.resize(n);
seen.assign(n, false);
for (int i = 0; i < n; ++i) {
if (!seen[i]) vals.push_back(dfs2(i));
}
sort(vals.rbegin(), vals.rend());
int maxD = 0;
seen.assign(n, false);
for (int i = 0; i < n; ++i) {
if (!seen[i]) maxD = max(maxD, diameter(i));
}
if (vals.size() >= 2) maxD = max(maxD, vals[0] + L + vals[1]);
if (vals.size() >= 3) maxD = max(maxD, vals[1] + 2*L + vals[2]);
return maxD;
}
