#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
int pa[N];
vector < int > adj[N];
map < int , int > dist;
map < pair < int , int > , int > we;
vector < int > par(N, -1);
int find(int u){
if(par[u] < 0)return u;
else return par[u] = find(par[u]);
}
void uni(int u, int v){
u = find(u);
v = find(v);
if(u == v)return;
par[u] += par[v];
par[v] = u;
}
void dfs(int u, int p = -1){
for(auto v : adj[u]){
if(v != p){
dist[v] = dist[u] + we[{u, v}];
dfs(v, u);
}
}
}
void dfs_(int u, int end, int p = -1){
pa[u] = p;
for(auto v : adj[u]){
if(v != p)
dfs_(v, end, u);
}
}
pair < int , int > centre(int st, int end){
int sz = 0;
vector < int > path = {end};
while(end != st){
sz += we[{end, pa[end]}];
end = pa[end];
path.push_back(end);
}
int mn = sz, diametr = sz, cur = 0, node = path[0], far;
for(int i = 1; i < path.size(); i++){
int W = we[{path[i], path[i - 1]}];
sz -= W;
cur += W;
if(mn > max(sz, cur)){
if(sz > cur)far = path.back();
else far = path[0];
mn = max(sz, cur);
node = path[i];
}
}
return {diametr, node};
}
pair < int , int > find_diametr(int Node){
dfs(Node);
int mx = 0, u = Node, v = Node;
for(auto e : dist){
int node = e.first;
int dis = e.second;
if(dis > mx){
mx = dis;
u = node;
}
}
mx = 0;
dist.clear();
dfs(u);
for(auto e : dist){
int node = e.first;
int dis = e.second;
if(dis > mx){
mx = dis;
v = node;
}
}
dist.clear();
dfs_(u, v);
return {u, v};
}
int travelTime(int n, int m, int L, int u[], int v[], int w[]){
for(int i = 0; i < m; i++){
we[{u[i], v[i]}] = w[i];
we[{v[i], u[i]}] = w[i];
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
uni(u[i], v[i]);
}
set < int > cmps;
for(int i = 0; i < n; i++)
cmps.insert(find(i));
vector < pair < int , int > > x;
for(auto nd : cmps){
pair < int , int > p = find_diametr(nd);
int u = p.first;
int v = p.second;
x.push_back(centre(u, v));
}
sort(x.rbegin(), x.rend());
int Node = x[0].second;
for(int i = x.size() - 1; i >= 1; i--){
adj[Node].push_back(x[i].second);
adj[x[i].second].push_back(Node);
we[{Node, x[i].second}] = L;
we[{x[i].second, Node}] = L;
}
pair < int , int > p = find_diametr(Node);
int U = p.first;
int V = p.second;
return centre(U, V).first;
}
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
