#include "dreaming.h"
#include <bits/stdc++.h>
#include <complex.h>
using namespace std;
const int maxn = 1e5+5;
typedef struct Trail {
int node;
int time;
int diam;
} trail;
vector<trail> tree[maxn];
trail mais_distante;
vector<trail> centros;
void dfs(int u, int tempo[], int pai[]) {
if (tempo[u] > mais_distante.time) {
mais_distante.time = tempo[u];
mais_distante.node = u;
}
for (auto V:tree[u]) {
int v = V.node;
int t = V.time;
if (v == pai[u]) continue;
tempo[v] = tempo[u] + t;
pai[v] = u;
dfs(v, tempo, pai);
}
}
trail backtrack(int node, int tempo[], int pai[]) {
int diam = tempo[node];
trail centro = {-1, (int) 2e9};
while (node != -1) {
int maior = max(tempo[node], diam - tempo[node]);
if (maior < centro.time)
centro = {node, maior};
node = pai[node];
}
centro.diam = diam;
return centro;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i++) {
tree[ A[i] ].push_back({B[i], T[i]});
tree[ B[i] ].push_back({A[i], T[i]});
}
int tempo1[N];
int tempo2[N];
memset(tempo1, 0, sizeof(tempo1));
memset(tempo2, 0, sizeof(tempo2));
int pai1[N];
int pai2[N];
memset(pai1, -1, sizeof(pai1));
memset(pai2, -1, sizeof(pai2));
for (int i = 0; i < N; i++) {
//Se i não faz parte duma árvore avaliada
if (tempo1[i] == 0) {
mais_distante = {-1, -1};
//busca 1
pai1[i] = -1;
dfs(i, tempo1, pai1);
//busca 2
pai2[mais_distante.node] = -1;
mais_distante.time = -1;
dfs(mais_distante.node, tempo2, pai2); //O caminho até o mais distante deste é o diâmetro
centros.push_back(backtrack(mais_distante.node, tempo2, pai2)); //Achando o centro
}
}
//Agora vamos unir os centros!
trail resposta = {centros[0].node, centros[0].time, centros[0].diam};
for (int i = 1; i < (int) centros.size(); i++) {
trail atual = centros[i];
//O diâmetro é o maior entre o atual e a ligação nova
if (resposta.diam < resposta.time + L + atual.time) { //Se o diãmetro antigo é menor
resposta.diam = resposta.time + L + atual.time;
//Qual deve ser o novo centro
int op1 = max(resposta.diam - resposta.time - L, atual.time); //O nó novo?
int op2 = max(resposta.diam - atual.time - L, resposta.time); //O antigo?
if (op1 < op2) //Se precisa ser o nó novo
resposta.node = atual.node, resposta.time = op1;
else { //Se pode ser o atual
resposta.time = op2;
}
}
}
return resposta.diam;
}
