/**
____ ____ ____ ____ ____
||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> centers;
vector <int> weights;
{
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;
int center = -1;
for(int v : nodes)
{
int maxDist = max(maxDistDown[v], maxDistUp[v]);
if(maxDist < bestMaxDist)
{
bestMaxDist = maxDist;
center = v;
}
}
centers.push_back(center);
weights.push_back(bestMaxDist);
}
}
sort(weights.begin(), weights.end());
if(n == 1)
return weights.end()[-1];
else if(n == 2)
return weights.end()[-1] + weights.end()[-2] + lenNew;
else
return max(weights.end()[-2] + weights.end()[-3] + lenNew * 2, weights.end()[-1] + weights.end()[-2] + lenNew);
}
