#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> pii;
const int MAXN=100005;
vector<pii> adj[MAXN];
vector<int> component;
int idx,jarak[MAXN],tree[4*MAXN],lazy[4*MAXN],ST[MAXN],EN[MAXN],preorder[MAXN];
bool visited[MAXN];
void dfs(int now,int par,int dist){
visited[now]=true;
idx++;
ST[now]=idx;
jarak[now]=dist;
preorder[idx]=now;
for(auto nxt : adj[now]){
if(nxt.first==par)continue;
dfs(nxt.first,now,dist+nxt.second);
}
EN[now]=idx;
}
void updatenode(int now,int L,int R,int val){
tree[now]+=val;
lazy[now]+=val;
}
void pushdown(int now,int L,int R){
int mid=(L+R)/2;
updatenode(2*now,L,mid,lazy[now]);
updatenode(2*now+1,mid+1,R,lazy[now]);
lazy[now]=0;
}
void build(int now,int L,int R){
lazy[now]=0;
if(L==R){
tree[now]=jarak[preorder[L]];
return;
}
int mid=(L+R)/2;
build(2*now,L,mid);
build(2*now+1,mid+1,R);
tree[now]=max(tree[2*now],tree[2*now+1]);
}
void update(int now,int L,int R,int x,int y,int val){
if(L>=x && R<=y){
updatenode(now,L,R,val);
return;
}
if(L>y || R<x)return;
pushdown(now,L,R);
int mid=(L+R)/2;
update(2*now,L,mid,x,y,val);
update(2*now+1,mid+1,R,x,y,val);
tree[now]=max(tree[2*now],tree[2*now+1]);
}
int query(int now,int L,int R,int x,int y){
if(L>=x && R<=y)return tree[now];
if(L>y || R<x)return 0;
pushdown(now,L,R);
int mid=(L+R)/2;
return max(query(2*now,L,mid,x,y),query(2*now+1,mid+1,R,x,y));
}
int furthest,diameter;
void dfsR(int now,int par){
int leafTerjauh=query(1,1,idx,1,idx);
furthest=min(furthest,leafTerjauh);
diameter=max(diameter,leafTerjauh);
for(auto nxt : adj[now]){
if(nxt.first==par)continue;
update(1,1,idx,1,idx,nxt.second);
update(1,1,idx,ST[nxt.first],EN[nxt.first],-2*nxt.second);
dfsR(nxt.first,now);
update(1,1,idx,1,idx,-nxt.second);
update(1,1,idx,ST[nxt.first],EN[nxt.first],2*nxt.second);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
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]});
}
vector<int> v;
int ans=0;
for(int i=0;i<N;i++){
//for every tree, find root s.t the distance between the root and the furthest leaf is minimum
if(visited[i])continue;
idx=0;
dfs(i,-1,0);
build(1,1,idx);
furthest=1e9;
diameter=0;
dfsR(i,-1);
ans=max(ans,diameter);
v.push_back(furthest);
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
if(v.size()==2)ans=max(ans,v[0]+v[1]+L);
else if(v.size()>=3){
int ret=1e9;
ret=min(ret,max(v[0]+v[1]+L,v[1]+v[2]+2*L));
ret=min(ret,max(v[0]+v[1]+L,v[0]+v[2]+2*L));
ret=min(ret,max(v[0]+v[1]+2*L,v[0]+v[2]+L));
ans=max(ans,ret);
}
return ans;
}
