#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> ii;
int ans, far;
vector<int> dis, sz;
vector<vector<ii>> adj;
void dfs(int cur, int par) {
if (dis[cur] > dis[far]) far = cur;
sz[cur] = 1;
ans = max(ans,dis[cur]);
for (auto nx : adj[cur]) {
if (nx.fi == par) continue;
dis[nx.fi] = dis[cur]+nx.se;
dfs(nx.fi,cur);
sz[cur] += sz[nx.fi];
}
}
int centroid(int cur, int par, int sub) {
for (auto nx : adj[cur]) {
if (nx.fi == par) continue;
if (sz[nx.fi]*2 >= sub) return centroid(nx.fi,cur,sub);
}
return cur;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj = vector<vector<ii>>(N+5);
for (int i = 0; i < M; i++) {
A[i]++, B[i]++;
adj[A[i]].push_back(ii(B[i],T[i]));
adj[B[i]].push_back(ii(A[i],T[i]));
}
dis = sz = vector<int>(N+5,0);
vector<int> com;
for (int i = 1; i <= N; i++) {
if (!sz[i]) {
// get this component's diameter
dis[i] = 0; far = i; dfs(i,-1);
dis[far] = 0; dfs(far,-1);
// get this component's centroid
dis[i] = 0; far = i; dfs(i,-1);
int cent = centroid(i,-1,sz[i]);
dis[cent] = 0; far = cent; dfs(cent,-1);
com.push_back(dis[far]);
}
}
sort(com.rbegin(),com.rend());
if (com.size() >= 2) ans = max(ans,com[0]+com[1]+L);
if (com.size() >= 3) ans = max(ans,com[1]+com[2]+2*L);
return ans;
}
