#include <bits/stdc++.h>
#include "dreaming.h"
#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;
const int MAXN = 1e5 + 5, INF = 1e9 + 5;
using ll = long long;
struct Edge {
int u, v, w;
Edge(int u, int v, int w) : u(u), v(v), w(w) {}
};
vector<vector<pair<int, int>>> g, gComp;
vector<pair<int, int>> bestComps;
vector<vector<Edge>> components;
bool vis[MAXN];
pair<int, int> leaf[2];
int mx;
pair<int, int> optimalRoot;
int diameterDist[MAXN][2];
// Find the nodes in this tree in the forest
void dfs(int u, int p) {
vis[u] = true;
if (p == -1) {
components.back().emplace_back(u, u, 0);
}
for (const auto &[v, wt] : g[u]) {
if (vis[v]) continue;
dfs(v, u);
components.back().emplace_back(u, v, wt);
}
}
void diameter(vector<vector<pair<int, int>>> &graph, int u, int p, int dist, int idx) {
leaf[idx] = max(leaf[idx], make_pair(dist, u));
diameterDist[u][idx] = dist;
optimalRoot = min(optimalRoot, make_pair(max(diameterDist[u][0], diameterDist[u][1]), u));
for (const auto &[v, wt] : g[u]) {
if (v == p) continue;
diameter(graph, v, u, dist + wt, idx);
}
}
// Find the centre of the weighted tree
void findRoot(int idx) {
// cout << "####### COMPONENT NUMBER: " << idx + 1 << " ##########\n";
// Setup the graph for the tree in the forest
for (const auto &[u, v, wt] : components[idx]) {
gComp[u].emplace_back(v, wt);
gComp[v].emplace_back(u, wt);
// cout << u << " " << v << "\n";
}
// cout << "\n";
// Root the tree at the first node in the component
int curRoot = components[idx].front().u;
leaf[0] = leaf[1] = {-INF, -INF};
// Find the farthest point from the asummed root
diameter(gComp, curRoot, -1, 0, 0);
// Find the other leaf of the diameter, compute distances to each node from the first leaf of the diaemeter
diameter(gComp, leaf[0].second, -1, 0, 1);
// Compute distances to each node from the second leaf of the diameter
optimalRoot = {INF, curRoot};
diameter(gComp, leaf[1].second, -1, 0, 0);
// cout << "Diameter distances:\n";
// for (const auto &[u, v, wt] : components[idx]) {
// cout << u << " " << diameterDist[u][0] << " " << diameterDist[u][1] << "\n";
// cout << v << " " << diameterDist[v][0] << " " << diameterDist[v][1] << "\n";
// }
// cout << "\n";
// cout << "Optimal Root: " << optimalRoot.second << "\n\n";
// Clear the tree in forest graph
for (const auto &[u, v, wt] : components[idx]) {
gComp[u].clear();
gComp[v].clear();
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
g.resize(MAXN);
gComp.resize(MAXN);
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 all trees in the forest
for (int i = 0; i < N; i++) {
if (vis[i]) continue;
components.emplace_back();
dfs(i, -1);
}
// Find the weighted centre of each tree in the forest
for (int i = 0; i < int(components.size()); i++) {
findRoot(i);
// optimalRoot --> (max cost to any node, root)
bestComps.emplace_back(optimalRoot.first, optimalRoot.second);
}
// Sort components in non increasing order of weighted centre
sort(bestComps.begin(), bestComps.end(), greater<>());
// Root of the tree with maximum weighted centre
int best = bestComps.front().second;
// cout << "Best: " << best << "\n";
// Add edges from the maximum weighted centre to the weighted centre of all other trees
for (int i = 1; i < int(bestComps.size()); i++) {
// Pair --> (distance, root)
int v = bestComps[i].second;
g[best].emplace_back(v, L);
g[v].emplace_back(best, L);
}
leaf[0] = leaf[1] = {-INF, -INF};
// Find the diameter of the resulting tree
diameter(g, 0, -1, 0, 0);
diameter(g, leaf[0].second, -1, 0, 1);
// Pair --> (diameter, leaf)
return leaf[1].first;
}
// void solve() {
// int N, M, L;
// cin >> N >> M >> L;
// int A[M], B[M], T[M];
// for (int i = 0; i < M; i++)
// cin >> A[i] >> B[i] >> T[i];
// cout << travelTime(N, M, L, A, B, T) << "\n";
// }
// signed main() {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// int tc = 1;
// // cin >> tc;
// while (tc--) solve();
// }
