#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
std::vector<std::list<pair<int, int>>> adj_list;
int max_length_path = 0;
void dfs(int root, std::vector<int>& parent, std::vector<std::vector<int>>& pre_long, std::vector<std::vector<int>>& post_long) {
int child = 0;
for(auto& i : adj_list[root])
if(i.first!=parent[root]) {
parent[i.first] = root;
dfs(i.first, parent, pre_long, post_long);
if(child>0)
pre_long[root][child] = max(pre_long[root][child-1], i.second + (adj_list[i.first].size()>1?pre_long[i.first][0]:0));
else
pre_long[root][child] = i.second + (adj_list[i.first].size()>1?pre_long[i.first][0]:0);
post_long[root][child] = i.second + (adj_list[i.first].size()>1?pre_long[i.first][0]:0);
child++;
}
return;
}
int findLongestDistances(int root, std::vector<int>& parent, std::vector<std::vector<int>>& pre_long, std::vector<std::vector<int>>& post_long) {
int child = 0;
for(int i = post_long[root].size()-2; i>=0; i--)
post_long[root][i] = max(post_long[root][i], post_long[root][i+1]);
int min_dist = (adj_list[root].size()>0)?post_long[root][0]:0;
max_length_path = max(max_length_path, min_dist);
for(auto& i : adj_list[root])
if(i.first!=parent[root]) {
post_long[i.first][adj_list[i.first].size()-1] = max(child>0?pre_long[root][child-1]:0, child<(adj_list[root].size()-1)?post_long[root][child+1]:0) + i.second;
if(adj_list[i.first].size()>1)
pre_long[i.first][adj_list[i.first].size()-1] = max(pre_long[i.first][adj_list[i.first].size()-2], post_long[i.first][adj_list[i.first].size()-1]);
else
pre_long[i.first][adj_list[i.first].size()-1] = post_long[i.first][adj_list[i.first].size()-1];
min_dist = min(min_dist, findLongestDistances(i.first, parent, pre_long, post_long));
child++;
}
return min_dist;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj_list.assign(N, std::list<pair<int, int>> ());
max_length_path = 0;
std::vector<std::vector<int>> pre_long(N, std::vector<int> ()), post_long(N, std::vector<int> ());
std::vector<int> parent(N, -1), trees;
for(int i = 0; i<M; i++) {
adj_list[A[i]].push_back({B[i], T[i]});
adj_list[B[i]].push_back({A[i], T[i]});
}
for(int i = 0; i<N; i++) {
pre_long[i].resize(adj_list[i].size());
post_long[i].resize(adj_list[i].size());
}
for(int i = 0; i<N; i++) {
if(parent[i]==-1) {
dfs(i, parent, pre_long, post_long);
int dist = findLongestDistances(i, parent, pre_long, post_long);
trees.push_back(dist);
}
}
sort(trees.begin(), trees.end());
int i = trees.size()-1;
if(trees.size()>1) {
max_length_path = max(max_length_path, trees[i-1]+trees[i]+L);
if(trees.size()>2)
max_length_path = max(max_length_path, trees[i-1]+trees[i-2]+2*L);
}
return max_length_path;
}
