#include "dreaming.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=1e5+5;
int n,m,cnt,l[N],r[N],Time,root,dep[N],last,ST[4*N],lazy[4*N];
pii val[N];
vector<int>adj[N];
vector<pii>g[N];
bool vis[N];
vector<int>go;
void dolazy(int id,int l,int r)
{
if (lazy[id]==0) return;
ST[id]+=lazy[id];
if (l!=r)
{
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
}
lazy[id]=0;
}
void update(int id,int l,int r,int L,int R,int val)
{
dolazy(id,l,r);
if (r<L||R<l) return;
if(L<=l&&r<=R)
{
ST[id]+=val;
if (l!=r)
{
lazy[id*2]+=val;
lazy[id*2+1]+=val;
}
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,L,R,val);
update(id*2+1,mid+1,r,L,R,val);
ST[id]=max(ST[id*2],ST[id*2+1]);
}
int get (int id,int l,int r,int L,int R)
{
dolazy(id,l,r);
if (r<L||R<l) return -1e9;
if (L<=l&&r<=R) return ST[id];
int mid=(l+r)/2;
return max (get (id*2,l,mid,L,R),get (id*2+1,mid+1,r,L,R));
}
void dfs(int u)
{
go.push_back(u);
vis[u]=true;
Time++;
l[u]=Time;
for(auto&id:adj[u])
{
int v=a[id]+b[id]-u;
if(vis[v]) continue;
dep[v]=dep[u]+w[id];
dfs(v);
}
r[u]=Time;
}
void calc(int u)
{
vis[u]=true;
val[cnt]=min(val[cnt],mp(get(1,1,n,l[root],r[root]),u));
//if(root==0) cout<<u<<' '<<l[root]<<' '<<r[root]<<' '<<get(1,1,n,l[root],r[root])<<' '<<val[cnt].fi<<'\n';
for(auto&id:adj[u])
{
int v=a[id]+b[id]-u;
if(vis[v]) continue;
update(1,1,n,l[root],r[root],w[id]);
update(1,1,n,l[v],r[v],-2*w[id]);
calc(v);
update(1,1,n,l[root],r[root],-w[id]);
update(1,1,n,l[v],r[v],2*w[id]);
}
}
void fin(int u,int p)
{
if(dep[u]>dep[last]) last=u;
for(auto&v:g[u])
{
if(v.fi==p) continue;
dep[v.fi]=dep[u]+v.se;
fin(v.fi,u);
}
}
int travelTime(int num,int m,int t,int a[],int b[],int w[])
{
n=num;
for(int i=0;i<m;i++)
{
adj[a[i]].push_back(i);
adj[b[i]].push_back(i);
}
cnt=0;
for(int i=0;i<n;i++)
{
if(!vis[i])
{
root=i;
go.clear();
dfs(i);
for(auto&u:go)
{
//if(!i) cout<<l[u]<<' '<<dep[u]<<'\n';
vis[u]=false;
update(1,1,n,l[u],l[u],dep[u]);
}
//cout<<'\n';
cnt++;
val[cnt]=mp(1e9,0);
calc(i);
//cout<<val[cnt].fi<<'\n';
}
}
sort(val+1,val+cnt+1);
int p=val[cnt].se;
for(int i=cnt-1;i>=1;i--)
{
g[p].push_back(mp(val[i].se,t));
g[val[i].se].push_back(mp(p,t));
//cout<<val[i].se<<' '<<p<<' '<<t<<'\n';
}
for(int i=0;i<m;i++)
{
g[a[i]].push_back(mp(b[i],w[i]));
g[b[i]].push_back(mp(a[i],w[i]));
//cout<<a[i]<<' '<<b[i]<<' '<<w[i]<<'\n';
}
fin(0,-1);
dep[last]=0;
fin(last,-1);
return dep[last];
}
/*
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int l;
cin>>n>>m>>l;
a.resize(m),b.resize(m),w.resize(m);
for(int i=0;i<m;i++) cin>>a[i];
for(int i=0;i<m;i++) cin>>b[i];
for(int i=0;i<m;i++) cin>>w[i];
cout<<travelTime(n,m,l,a,b,w);
}
12 8 2
0 8 2 5 5 1 1 10
8 2 7 11 1 3 9 6
4 2 4 3 7 1 5 3
*/
Compilation message
dreaming.cpp: In function 'void dfs(int)':
dreaming.cpp:66:15: error: 'a' was not declared in this scope
66 | int v=a[id]+b[id]-u;
| ^
dreaming.cpp:66:21: error: 'b' was not declared in this scope
66 | int v=a[id]+b[id]-u;
| ^
dreaming.cpp:68:23: error: 'w' was not declared in this scope
68 | dep[v]=dep[u]+w[id];
| ^
dreaming.cpp: In function 'void calc(int)':
dreaming.cpp:81:15: error: 'a' was not declared in this scope
81 | int v=a[id]+b[id]-u;
| ^
dreaming.cpp:81:21: error: 'b' was not declared in this scope
81 | int v=a[id]+b[id]-u;
| ^
dreaming.cpp:83:38: error: 'w' was not declared in this scope
83 | update(1,1,n,l[root],r[root],w[id]);
| ^
