#include "dreaming.h"
#include <bits/stdc++.h>
#define deb(x) cerr << #x <<": " << x << '\n';
using namespace std;
typedef vector<int> VI;
typedef pair<int,int> II;
const int INF = 1000000010;
struct Edge {
int to, weight;
};
typedef vector< vector<Edge> > Graph;
int N;
Graph billabongs;
vector<bool> vis;
VI component;
void dfs1(int src){
vis[src] = true;
component.push_back(src);
for(Edge e : billabongs[src]){
if(vis[e.to]) continue;
dfs1(e.to);
}
}
void dfs2(const Graph& tree, VI& D, int u, int d = 0) {
D[u] = d;
for (Edge e : tree[u]) {
if (D[e.to] >= 0) continue;
dfs2(tree, D, e.to, d+e.weight);
}
}
II get_center_points(const Graph& tree) {
const int n = tree.size();
if (n == 1)
return {0, 0};
//Longest path in a tree
// finding first endpoint of the tree
VI D1(n,-1);
int u_max = 0;
dfs2(tree,D1,0);
for(int u = 0; u < n; ++u) {
if (D1[u] > D1[u_max])
u_max = u;
}
//deb(u_max);
// finding the second endpoint of the tree
VI D2(n,-1);
int v_max = 0;
dfs2(tree,D2,u_max);
for(int v = 0; v < n; ++v) {
if (D2[v] > D2[v_max])
v_max = v;
}
//deb(v_max);
// filling the Distances for the second endpoint
VI D3(n,-1);
dfs2(tree,D3,v_max);
// finding the "center point"
II best = {INF,INF}, temp;
for(int u = 0; u < n; ++u){
if(D2[u] > D3[u])
temp = {D2[u], D3[u]};
else
temp = {D3[u], D2[u]};
best = min(best,temp);
}
return best;
}
Graph renumerate(){
map<int,int> new_id;
int n = (int) component.size();
for(int i = 0; i < n; ++i)
new_id[component[i]] = i;
Graph tree(n);
for(int u : component){
int new_id_of_u = new_id[u];
for(Edge e : billabongs[u]){
int new_id_of_v = new_id[e.to];
tree[new_id_of_u].push_back({new_id_of_v, e.weight});
//tree[new_id_of_v].push_back({new_id_of_u, e.weight}); not added because it was previously
// added when extracting the Graph (line 104)
}
}
return tree;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
::N = N;
//First part representing the Graph
billabongs = Graph(N);
for(int i = 0; i < M; ++i){
int u = A[i], v = B[i], weight = T[i];
billabongs[u].push_back({v,weight});
billabongs[v].push_back({u,weight});
}
vis = vector<bool>(N,false);
vector<Graph> trees;
//Second part getting the connected components (trees)
for(int i = 0; i < N; ++i){
if(vis[i]) continue;
component = VI(0);
dfs1(i);
//Third part renumerating the ids of the nodes of the trees
Graph tree = renumerate();
trees.emplace_back(tree);
}
//for testing
/*
int comp = 0;
for(Graph tree : trees){
cerr << "component # " << comp++ << '\n';
for(int j = 0; j < (int)tree.size(); ++j){
cerr << "Node: " << j << '\n';
for(Edge e : tree[j]){
cerr << "e.to: " << e.to << " e.weight: " << e.weight << '\n';
}
}
}
*/
//Fourth part getting the center points of the trees
vector<II> center_points;
for(Graph tree : trees){
II center_point = get_center_points(tree);
//cerr <<"center_point: " << center_point.first << ' ' << center_point.second << '\n';
center_points.push_back(center_point);
}
sort(center_points.begin(), center_points.end(), greater<II>());
int ans = 0;
//checking if the longest path is on the current tree;
for (II center_point : center_points)
ans = max(ans, center_point.first + center_point.second);
//checking if there are 2 or more center points
if (int(center_points.size()) > 1) {
ans = max(ans,center_points[0].first + L + center_points[1].first);
for (int i = 2; i < int(center_points.size()); ++i) {
ans = max(ans, center_points[i].first + 2*L + center_points[1].first);
}
}
return ans;
}
