#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int ,int>>> adj;
vector<int> center;
vector<bool> vis;
int mx = 0;
int y = 0;
int z = 0;
void dfs1(int x , int p = -1 , int d = 0)
{
vis[x] = 1;
if(mx <= d)
{
mx = d;
y = x;
}
for(auto [u , c] : adj[x])
{
if(u == p)
continue;
dfs1(u , x , d + c);
}
}
vector<pair<int ,int>> par;
void dfs2(int x , int p = -1 , int d = 0)
{
if(mx <= d)
{
mx = d;
z = x;
}
for(auto [u , c] : adj[x])
{
if(u == p)
continue;
par[u]= {x , c};
dfs2(u , x , d + c);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
adj.assign(N , {});
vis.assign(N , 0);
for(int i = 0 ; i < M; i++)
{
adj[A[i]].push_back({B[i] , T[i]});
adj[B[i]].push_back({A[i] , T[i]});
}
for(int i = 0 ; i < N ; i++)
{
if(!vis[i])
{
y = 0;
mx = 0;
dfs1(i);
mx = 0;
z = 0;
par.assign(N , {-1 , -1});
dfs2(y);
int sm = 0;
int mid = z;
while(par[z].first != -1 && 2 * sm < mx)
{
sm += par[z].second;
mid = par[z].first;
z = par[z].first;
}
center.push_back(mid);
}
}
adj[center[0]].push_back({center[1] ,L});
adj[center[1]].push_back({center[0] , L});
y = 0;
mx = 0;
vis.assign(N , 0);
dfs1(0 , -1 , 0);
mx = 0;
z = 0;
dfs2(y);
return mx;
}
