#include "dreaming.h"
#include <bits/stdc++.h>
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 60)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define ptr(A) shared_ptr<A>
using namespace std;
struct Edge {
ll node, wth;
};
struct Component {
ll diameter_length;
ll rep_max;
};
bool operator < (const Component& a, const Component& b) { return a.rep_max < b.rep_max; }
vector<vector<Edge>> adj;
vector<bool> memo;
pqueue<Component> comp;
ll max_d; ll max_i;
void find_furthest (ll i, ll from, ll cnt) {
memo[i] = 1;
if (max_d < cnt) {
max_d = cnt;
max_i = i;
}
for (auto& k : adj[i]) {
if (k.node != from)
find_furthest(k.node, i, cnt + k.wth);
}
}
vector<pair<ll, ll>> path;
ll dlength;
ll fill_path (ll i, ll from, ll cnt) {
path[i].first = cnt;
ll maxi = 0;
for (auto& k : adj[i]) {
if (k.node != from) {
maxi = max(maxi, k.wth + fill_path(k.node, i, cnt + k.wth));
}
}
path[i].second = maxi;
dlength = max(dlength, path[i].first + path[i].second);
return maxi;
}
ll min_abs, rep_i;
void find_rep(ll i, ll from) {
if (path[i].first + path[i].second == dlength) {
if (abs(path[i].first - path[i].second) < min_abs) {
min_abs = abs(path[i].first - path[i].second);
rep_i = i;
}
}
for (auto& k : adj[i]) {
if (k.node != from)
find_rep(k.node, i);
}
}
Component find_representative(ll i) {
max_d = -1;
find_furthest(i, i, 0);
max_d = -1;
dlength = -1;
fill_path(max_i, max_i, 0);
min_abs = INF64;
find_rep(i, i);
// cout << dlength << ' ' << max(path[rep_i].first, path[rep_i].second) << '\n';
return {dlength, max(path[rep_i].first, path[rep_i].second)};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj.resize(N);
memo.resize(N);
path.resize(N);
range(i, 0, M) {
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
range(i, 0, N) {
if (!memo[i]) {
// cout << "** " << i << '\n';
comp.push(find_representative(i));
}
}
while (comp.size() > 1) {
Component c1 = comp.top(); comp.pop();
Component c2 = comp.top(); comp.pop();
comp.push({max({c1.rep_max + c2.rep_max + L, c1.diameter_length, c2.diameter_length}), max(c1.rep_max, c2.rep_max) + L});
}
return comp.top().diameter_length;
}
