#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "dreaming.h"
using namespace std;
const int N = 3e5+1;
vector<pair<int, int>> g[N];
int dp[N];
int depth[N];
int mx[N];
bool vis[N];
vector<int> gag[2];
int o;
vector<pair<int,int>> hert;
void dfs2(int v,int p) {
mx[v] = depth[v];
for (auto i : g[v]) {
if (i.first == p) {
continue;
}
depth[i.first] = depth[v] + i.second;
dfs2(i.first,v);
mx[v] = max(mx[i.first], mx[v]);
}
dp[v] = mx[v] - depth[v];
vector<int> mas;
for (auto i : g[v]) {
if (i.first == p) {
continue;
}
mas.push_back(mx[i.first]);
}
if (mas.empty() || mas.size()==1) {
return;
}
sort(mas.rbegin(), mas.rend());
dp[v] = max(dp[v],mas[0] + mas[1] - 2*depth[v]);
}
int get() {
for (int i = 0;i < o;++i) {
dp[i] = 0;
mx[i] = 0;
depth[i] = 0;
}
dfs2(0,-1);
int answ = 0;
for (int i = 0;i < o;++i) {
answ = max(answ, dp[i]);
}
return answ;
}
void dfs(int v,int comp) {
vis[v] = 1;
gag[comp].push_back(v);
for (auto i : g[v]) {
if (!vis[i.first]) {
dfs(i.first, comp);
}
}
}
void dfs3(int v,int p,int dep) {
hert.push_back({v, dep });
for (auto i:g[v]) {
if (i.first == p) {
continue;
}
dfs3(i.first, v, dep + i.second);
}
}
int travelTime(int n, int m, int l,
int a[], int b[], int t[]) {
o = n;
for (int i = 0;i < m;++i) {
g[a[i]].push_back({ b[i], t[i] });
g[b[i]].push_back({ a[i],t[i] });
}
int cnt = 0;
for (int i = 0;i < n;++i) {
if (!vis[i]) {
dfs(i, cnt);
++cnt;
}
}
if (n <= 100) {
int answ = 1e9;
for (auto i : gag[0]) {
for (auto j : gag[1]) {
g[i].push_back({ j,l });
g[j].push_back({ i,l });
int p = get();
answ = min(answ, p);
g[i].pop_back();
g[j].pop_back();
}
}
return answ;
}
dfs3(gag[0][0], -1, 0);
int mn = 0;
int answ = 1e9;
for (auto i : hert) {
int h = max(i.second, hert.back().second - i.second);
if (answ > h) {
answ = h;
mn = i.first;
}
}
hert.clear();
dfs3(gag[1][0], -1, 0);
int mn2 = 0;
answ = 1e9;
for (auto i : hert) {
int h = max(i.second, hert.back().second- i.second);
if (answ > h) {
answ = h;
mn2 = i.first;
}
}
g[mn].push_back({ mn2,l });
g[mn2].push_back({ mn,l });
return get();
}
