#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include "dreaming.h"
using namespace std;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back
#define ll long long
#define ui uint64_t
#define ar array
#define us unordered_set
#define cont(set, element) ((set).find(element) != (set).end())
/********* DEBUG *********/
template <typename T>
void outvec(const vector<T>& Z){
for (const T& x : Z)
cout << x << ' ';
cout << "\n";
}
void printVariable(const any& var) {
if (!var.has_value()) {
cout << "null";
return;
}
if (var.type() == typeid(int)) {
cout << any_cast<int>(var);
} else if (var.type() == typeid(double)) {
cout << any_cast<double>(var);
} else if (var.type() == typeid(float)) {
cout << any_cast<float>(var);
} else if (var.type() == typeid(char)) {
cout << any_cast<char>(var);
} else if (var.type() == typeid(bool)) {
cout << (any_cast<bool>(var) ? "true" : "false");
} else if (var.type() == typeid(string)) {
cout << any_cast<string>(var);
} else if (var.type() == typeid(const char*)) {
cout << any_cast<const char*>(var);
} else if (var.type() == typeid(long long)) {
cout << any_cast<long long>(var);
} else {
cout << "[unknown type]";
}
}
template<typename... Args>
void outval(Args... args) {
vector<any> variables = {args...};
for (size_t i = 0; i < variables.size(); ++i) {
printVariable(variables[i]);
if (i != variables.size() - 1) {
cout << " ";
}
}
cout << "\n";
}
/********* DEBUG *********/
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
const ll MOD3 = 1000000000;
const ll needMOD = 987654321;
const ll mxN = 100005;
const ll inf = 1e18;
/* idea
answer is equal to max(top1 + top2 + L, top2 + top3 + L * 2, topdiameter)
just implement finding the diameter and radius of each connected component
*/
void solve() {
}
ll tpdia, ccrad[3], currdia, farnd, lorad, currad;
bool fndrad;
void updcc(ll val){
for (int i = 0; i < 3; i++){
if (val > ccrad[i]){
swap(val,ccrad[i]);
}
}
}
// return if we reach end leaf
bool dfs(ll nd, vector<vector<pair<ll,ll>>> &adj, ll par = -1, ll dep = 0){
if (dep > currdia){
currdia = dep;
farnd = nd;
}
bool reach = par != -1 && dep==tpdia;
//if (fndrad)
//cout << "cl nd, dep: " << nd << ' ' << dep << "\n";
for (auto &[newnd, cst] : adj[nd]){
if (newnd==par)
continue;
reach = reach | dfs(newnd, adj, nd, dep+cst);
}
if (fndrad && reach){
if (currad==0)
currad=max(dep,currdia-dep);
currad=min(currad, max(dep, currdia-dep));
adj[nd].clear();
}
return reach;
}
void take(ll nd, vector<vector<pair<ll,ll>>> &adj, ll cst = 0, ll par = -1){
farnd=currdia=fndrad=0;
dfs(nd, adj);
currdia=0;
//cout << farnd << "\n";
dfs(farnd, adj);
tpdia=max(tpdia, currdia);
// now we have diameter of the current CC = currdia
// find radius now
lorad=currad=0;
fndrad=true;
dfs(farnd, adj);
lorad=max(lorad,currad);
// now we have radius of graph, update the ccrads and done
updcc(currad);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
tpdia=0;
memset(ccrad, 0, 3);
// nd, cst
vector<vector<pair<ll,ll>>> adj(N);
for (int i = 0; i < M; i++){
adj[A[i]].pb({B[i], T[i]});
adj[B[i]].pb({A[i], T[i]});
}
for (int i = 0; i < N; i++){
if (sz(adj[i]) == 1){
take(i, adj);
}
}
int ans = tpdia;
if (M < N-1)
ans = max(ans, (int)ccrad[0] + (int)ccrad[1] + L);
if (M < N-2)
ans = max(ans, (int)ccrad[1] + (int)ccrad[2] + L * 2);
return ans;
}
