/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
struct Edge
{
int to;
int len;
};
int travelTime (int n, int m, int lenNew, int edgeU[], int edgeV[], int edgeL[])
{
vector <Edge> edges[n];
for(int i = 0; i < m; i++)
{
edges[edgeU[i]].push_back(Edge{edgeV[i], edgeL[i]});
edges[edgeV[i]].push_back(Edge{edgeU[i], edgeL[i]});
}
vector <int> weights;
int maxDiam = 0;
{
int plen[n];
int maxDistUp[n];
int maxDistDown[n];
int maxDistDown2[n];
bool visited[n];
vector <int> nodes;
function <void (int, int)> DFSDown = [&] (int u, int parent)
{
nodes.push_back(u);
visited[u] = true;
maxDistDown[u] = 0;
maxDistDown2[u] = 0;
for(Edge e : edges[u])
if(e.to != parent)
{
plen[e.to] = e.len;
DFSDown(e.to, u);
if(maxDistDown[e.to] + e.len >= maxDistDown[u])
{
maxDistDown2[u] = maxDistDown[u];
maxDistDown[u] = maxDistDown[e.to] + e.len;
}
else if(maxDistDown[e.to] + e.len > maxDistDown2[u])
maxDistDown2[u] = maxDistDown[e.to] + e.len;
}
};
function <void (int, int)> DFSUp = [&] (int u, int parent)
{
if(parent != -1)
{
maxDistUp[u] = maxDistUp[parent] + plen[u];
if(maxDistDown[u] + plen[u] == maxDistDown[parent])
maxDistUp[u] = max(maxDistUp[u], maxDistDown2[parent] + plen[u]);
else
maxDistUp[u] = max(maxDistUp[u], maxDistDown[parent] + plen[u]);
}
else
maxDistUp[u] = 0;
for(Edge e : edges[u])
if(e.to != parent)
DFSUp(e.to, u);
};
for(int u = 0; u < n; u++)
visited[u] = false;
for(int u = 0; u < n; u++)
if(visited[u] == false)
{
nodes.clear();
DFSDown(u, -1);
DFSUp(u, -1);
int bestMaxDist = INT_MAX;
for(int v : nodes)
{
int maxDist = max(maxDistDown[v], maxDistUp[v]);
maxDiam = max(maxDiam, maxDist);
bestMaxDist = min(bestMaxDist, maxDist);
}
weights.push_back(bestMaxDist);
}
}
sort(weights.begin(), weights.end());
if((int)weights.size() == 1)
return maxDiam;
else if((int)weights.size() == 2)
return max(weights.end()[-1] + weights.end()[-2] + lenNew,
maxDiam);
else
return max({weights.end()[-1] + weights.end()[-2] + lenNew,
weights.end()[-2] + weights.end()[-3] + lenNew * 2,
maxDiam});
}
