#include "dreaming.h" #include <bits/stdc++.h> using namespace std; using ll=long long; constexpr int MAXN=1e5+7; constexpr int INF=1e9+7; int t[MAXN]; int gl[MAXN]; int odl[MAXN][2]; vector<pair<int,int>> graf[MAXN]; pair<pair<int,int>,int> kraw[MAXN]; vector<int> spojna[MAXN]; int sigma[MAXN][2]; int srodek[MAXN]; int n,m,l; int Znajdz(int v){ if (v==t[v]) return v; t[v]=Znajdz(t[v]); return t[v]; } void Polacz(int a,int b){ a=Znajdz(a); b=Znajdz(b); if (gl[a]>gl[b]) swap(a,b); t[a]=b; if (gl[a]==gl[b]) gl[b]++; } void DFS(int v,int p,int c,bool x){ if (p==0) odl[v][x]=0; else odl[v][x]=odl[p][x]+c; for (pair<int,int> u:graf[v]){ if (u.first==p) continue; DFS(u.first,v,u.second,x); } } int solve(){ odl[0][0]=-1;odl[0][1]=-1; for (int i=1;i<=n;i++) t[i]=i; int a,b,c; for (int i=0;i<m;i++) Polacz(kraw[i].first.first,kraw[i].first.second); for (int i=1;i<=n;i++) spojna[Znajdz(i)].push_back(i); int turbo_srodek=-1; int mxo=-INF,o; for (int i=1;i<=n;i++){ if (t[i]!=i) continue; DFS(i,0,0,0); for (int v:spojna[i]){ if (odl[v][0]>odl[sigma[i][1]][0]) sigma[i][1]=v; } DFS(sigma[i][1],0,0,1); for (int v:spojna[i]){ if (odl[v][1]>odl[sigma[i][0]][1]) sigma[i][0]=v; } DFS(sigma[i][0],0,0,0); srodek[i]=i; for (int v:spojna[i]){ if (max(odl[v][0],odl[v][1])<max(odl[srodek[i]][0],odl[srodek[i]][1])) srodek[i]=v; } if (mxo<max(odl[srodek[i]][0],odl[srodek[i]][1])){ turbo_srodek=srodek[i]; mxo=max(odl[srodek[i]][0],odl[srodek[i]][1]); } } for (int i=1;i<=n;i++){ if (t[i]!=i) continue; if (srodek[i]==turbo_srodek) continue; graf[srodek[i]].push_back({turbo_srodek,l}); graf[turbo_srodek].push_back({srodek[i],l}); } DFS(1,0,0,0); a=0; for (int i=1;i<=n;i++){ if (odl[i][0]>odl[a][0]) a=i; } DFS(a,0,0,1); b=0; for (int i=1;i<=n;i++){ if (odl[i][1]>odl[b][1]) b=i; } return odl[b][1]; } int travelTime(int _n,int _m,int _l,int _A[],int _B[],int _T[]){ n=_n;m=_m;l=_l; int a,b,c; for (int i=0;i<m;i++){ a=_A[i];b=_B[i];c=_T[i]; a++;b++; graf[a].push_back({b,c}); graf[b].push_back({a,c}); kraw[i]={{a,b},c}; } return solve(); } //int main(){ // ios_base::sync_with_stdio(0); // cin.tie(0); //}