#include "dreaming.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define imie(...) " [" << #__VA_ARGS__ " :" << (__VA_ARGS__) << "] "
#define ed <<endl
const int mxn = 1e5+5;
vector<vector<pair<int, int>>> adj(mxn);
struct unionFind{
vector<int> par;
vector<int> rnk;
unionFind(int n){
par.resize(n);
rnk.resize(n);
for(int i=0;i<n;i++){
par[i]=i;
}
}
int find(int p){
if(par[p] != p){
par[p]=find(par[p]);
}
return par[p];
}
void join(int u, int v){
int uroot = find(u);
int vroot = find(v);
if(uroot == vroot){
return;
}
if(rnk[vroot] > rnk[uroot]) swap(uroot, vroot);
if(rnk[uroot] == rnk[vroot]) rnk[uroot]++;
par[vroot] = uroot;
}
};
vector<int> connected;
vector<int> mn(mxn, (1e9)+(1e8));
vector<vector<pair<int, int>>> ncosts(mxn);
int INF = 1e9+1;
int dfs1(int node, int par){
connected.push_back(node);
// cerr << imie(node) imie(curcost) ed;
if(adj[node].size() == 1 && adj[node][0].first == par){
mn[node]=0;
return 0;
}
vector<pair<int, int>> costs;
int mx=0;
for(int i=0;i<adj[node].size();i++){
int c = adj[node][i].second;
int v=adj[node][i].first;
if(v == par or v == node) continue;
// cerr << imie(node) imie(v) ed;
costs.push_back({dfs1(v, node)+c, v});
mx=max(mx, costs.back().first);
}
mn[node] = min(mn[node], mx);
sort(costs.begin(), costs.end());
ncosts[node] = costs;
return mx;
}
void dfs2(int node, int par, int ppar){
mn[node] = max(mn[node], ppar);
for(pair<int, int> i : adj[node]){
int c=i.second;
int v=i.first;
if(v != par){
if(ncosts[node].size() <= 1){
dfs2(v, node, ppar+c);
} else{
int mx = ppar;
if(ncosts[node].back().second == v){
int sz=ncosts[node].size();
mx = max(mx, ncosts[node][sz-2].first);
} else{
mx = max(mx, ncosts[node].back().first);
}
dfs2(v, node, mx+c);
}
}
}
}
int ans = 0;
int dfs(int node, int par){
vector<int> cur;
int mx =0;
for(pair<int, int> i : adj[node]){
int v=i.first;
int c=i.second;
if(v == par) continue;
cur.push_back(dfs(v, node)+c);
}
cur.push_back(0);
cur.push_back(0);
sort(cur.begin(), cur.end(), greater<int>());
mx=cur[0];
int other = cur[1];
ans = max(ans, mx + other);
return mx;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
unionFind uf(n);
for(int i=0;i<m;i++){
int u=a[i];
int v=b[i];
int c=t[i];
// cerr << imie(u) imie(v) ed;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
uf.join(u, v);
}
vector<int> vis(n);
vector<int> bests;
int mx=-1;
int center = -1;
for(int i=0;i<n;i++){
if(!vis[uf.find(i)]){
//find a
dfs1(uf.find(i), -1);
dfs2(uf.find(i), -1, 0);
int mns = INF;
int no = -1;
for(int i : connected){
if(mn[i] < mns){
no = i;
mns = mn[i];
}
}
if(mns > mx){
center = no;
mx = mns;
}
bests.push_back(no);
connected.clear();
vis[uf.find(i)] = 1;
}
}
for(int i=0;i<bests.size();i++){
if(bests[i] == center) continue;
adj[center].push_back({bests[i], l});
adj[bests[i]].push_back({center, l});
}
dfs(center, -1);
return ans;
}
