#include "dreaming.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sz(v) v.size()
#define all(v) (int)v.begin(),v.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=2e9;
const int N=1e5+11;
vector<pii>g[N];
struct Tree{
int root,diam,u,v,rad;
}T[N];
int par[N],comp[N],h[N],d[N];
int up[N][20];
bool used[N];
void addV(int v){
up[v][0]=par[v];
for(int i=1;i<=16;i++){
up[v][i]=up[up[v][i-1]][i-1];
}
}
int lca(int a,int b){
if(h[a]<h[b])swap(a,b);
int log;
for(log=1;(1<<log)<=h[a];log++);
log--;
for(int i=log;i>=0;i--){
if(h[a]-(1<<i)>=h[b]){
a=up[a][i];
}
}
if(a==b)return a;
for(int i=log;i>=0;i--){
if(up[a][i]!=0&&up[a][i]!=up[b][i]){
a=up[a][i],b=up[b][i];
}
}
return par[a];
}
void add(Tree &t,int b){
int l=lca(t.u,b);
int diam1=d[b]+d[t.u]-2*d[l];
l=lca(t.v,b);
int diam2=d[b]+d[t.v]-2*d[l];
int diam3=t.diam;
if(diam3>=diam1&&diam3>=diam2);
else if(diam2>=diam1&&diam2>=diam3){
t.diam=diam2;
t.u=b;
}
else {
t.diam=diam1;
t.v=b;
}
}
void bfs(int s){
queue<int>q;
q.push(s);
used[s]=1;
addV(s);
d[s]=0;
h[s]=0;
while(!q.empty()){
int v=q.front();
q.pop();
for(int i=0;i<sz(g[v]);i++){
int to=g[v][i].x;
if(!used[to]){
par[to]=v;
d[to]=d[v]+g[v][i].y;
h[to]=h[v]+1;
addV(to);
add(T[comp[v]],to);
q.push(to);
used[to]=1;
comp[to]=comp[v];
}
}
}
}
int travelTime(int n,int M,int L,vector<int>a,vector<int>b,vector<int>t){
for(int i=1;i<=n;i++){
par[i]=0;
comp[i]=i;
T[i]=Tree{i,0,i,i,0};
}
for(int i=0;i<M;i++){
g[a[i]+1].pb(mp(b[i]+1,t[i]));
g[b[i]+1].pb(mp(a[i]+1,t[i]));
}
for(int i=1;i<=n;i++){
if(!used[i]){
bfs(i);
}
}
for(int i=1;i<=n;i++){
used[i]=0;
}
vector<pii>Comp;
for(int i=1;i<=n;i++){
if(!used[comp[i]]){
int u=T[comp[i]].u;
int v=T[comp[i]].v;
int l=lca(u,v);
vector<int>path1;
vector<int>edg;
while(u!=l){
path1.pb(u);
u=par[u];
}
vector<int>path2;
while(v!=l){
path2.pb(v);
v=par[v];
}
path1.pb(l);
while(!path2.empty()){
path1.pb(path2.back());
path2.pop_back();
}
int len=0;
bool w=0;
T[comp[i]].rad=inf;
for(int j=0;j<sz(path1);j++){
if(j>0){
if(!w)len+=d[path1[j-1]]-d[path1[j]];
else len+=d[path1[j]]-d[path1[j-1]];
}
if(path1[j]==l)w=1;
int val=max(len,T[comp[i]].diam-len);
if(val<T[comp[i]].rad){
T[comp[i]].rad=val;
T[comp[i]].root=path1[j];
}
}
used[comp[i]]=1;
Comp.pb(mp(T[comp[i]].rad,comp[i]));
}
}
sort(all(Comp),greater<>());
int ans=0;
for(int i=0;i<sz(Comp);i++){
ans=max(ans,T[Comp[i].y].diam);
}
if(sz(Comp)>1){
if(ans<Comp[0].x+Comp[1].x+L){
ans=Comp[0].x+Comp[1].x+L;
}
if(sz(Comp)>2){
if(ans<Comp[1].x+Comp[2].x+2*L){
ans=Comp[1].x+Comp[2].x+2*L;
}
}
}
return ans;
}
/*
int main(){
int n,m,l;
cin>>n>>m>>l;
vector<int>a,b,t;
for(int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
a.pb(u);
b.pb(v);
t.pb(w);
}
cout<<travelTime(n,m,l,a,b,t);
}*/
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 9 5
1 3 1
6 10 3
*/
Compilation message
dreaming.cpp: In function 'void bfs(int)':
dreaming.cpp:83:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<sz(g[v]);i++){
^
dreaming.cpp: In function 'int travelTime(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
dreaming.cpp:142:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<sz(path1);j++){
^
dreaming.cpp:11:29: error: invalid cast from type 'std::vector<std::pair<int, int> >::iterator {aka __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >}' to type 'int'
#define all(v) (int)v.begin(),v.end()
^
dreaming.cpp:158:8: note: in expansion of macro 'all'
sort(all(Comp),greater<>());
^~~
dreaming.cpp:160:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<sz(Comp);i++){
^
