#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
pair<int, int> createTree(int n, int* tree, bool* visited, vector<unordered_map<int, int>> &graph, pair<pair<int, int>, pair<int, int>>* depth, unordered_set<int> &nodes){
visited[n] = true;
nodes.insert(n);
// depth[n].first = {d.first, dist};
for(const pair<int, int> &child : graph[n]){
if(visited[child.first]) continue;
tree[child.first] = n;
pair<int, int> d = createTree(child.first, tree, visited, graph, depth, nodes);
int dist = d.second + child.second;
// cout << "| " << n << ' ' << child.first << ' ' << dist << '\n';
if(dist > depth[n].first.second){
// cout << "Swapped: " << depth[n].first.first << ' ' << child.first << '\n';
depth[n].second = make_pair(child.first, dist);
swap(depth[n].second, depth[n].first);
}else if(dist > depth[n].second.second){
// cout << "Swapped: " << depth[n].second.first << ' ' << child.first << '\n';
// cout << "??: " << depth[n].second.second << ' ' << dist << '\n';
depth[n].second = make_pair(child.first, dist);
}else{
// cout << "didnt make it :(\n";
}
}
return depth[n].first;
}
void dfsUPUP(int node, bool* visited, int* up, int* upup, int prev, vector<unordered_map<int, int>> &graph){
visited[node] = node;
for(const pair<int, int> &child : graph[node]){
if(visited[child.first]) continue;
dfsUPUP(child.first, visited, up, upup, max(up[child.first], child.second + prev), graph);
}
upup[node] = prev;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
bool visited[100005] = {false};
int t = N-M-1;
vector<int> radii(t+1);
vector<int> diameter(t+1);
vector<unordered_map<int, int>> graph(N);
for(int i = 0; i < M; i++){
graph[A[i]][B[i]] = T[i];
graph[B[i]][A[i]] = T[i];
}
int tree[100005] = {-1};
pair<pair<int, int>, pair<int, int>> depth[100005];
for(int i = 0; i < 100005; i++) depth[i] = {{-1,0}, {-1,0}};
int up[100005] = {0};
bool upupVisited[100005] = {false};
int upup[100005] = {0};
int index = -1;
for(int root = 0; root < N; root++){
if(visited[root]) continue;
cout << "tree\n";
cout << "root: " << root << '\n';
unordered_set<int> nodes;
createTree(root, tree, visited, graph, depth, nodes);
index++;
// cout << "depth: ";
// for(const int &node : nodes) cout << node << ":" <<
// depth[node].first.first << ',' << depth[node].first.second
// << "(" << depth[node].second.first << ',' << depth[node].second.second << ' ';
// cout << '\n';
if(nodes.size() == 1){
radii[index] = 0;
diameter[index] = 0;
}
for(const int &node : nodes){
if(tree[node] == -1) continue;
if(depth[tree[node]].first.first == node){
up[node] = depth[tree[node]].second.second + graph[node][tree[node]];
}else{
up[node] = depth[tree[node]].first.second + graph[node][tree[node]];
}
}
// cout << "up: ";
// for(const int &node : nodes) cout << node << ":" << up[node] << ' ';
// cout << '\n';
dfsUPUP(root, upupVisited, up, upup, 0, graph);
int radius = INT_MAX;
int dm = 0;
for(const int &node : nodes){
radius = min(radius, max(upup[node], depth[node].first.second));
dm = max(dm, max(upup[node], depth[node].first.second));
}
radii[index] = radius;
diameter[index] = dm;
}
for(int i = 0; i < t+1; i++){
cout << radii[i] << ' ';
}
cout << '\n';
for(int i = 0; i < t+1; i++){
cout << diameter[i] << ' ';
}
cout << '\n';
int mxDist = 0;
int mxRad = -1;
int mxRad1 = -1;
for(int i = 0; i < t+1; i++) mxDist = max(mxDist, diameter[i]);
for(int i = 1; i < t+1; i++) {
mxDist = max(mxDist, radii[0] + L + radii[i]);
if(radii[i] > mxRad){
mxRad1 = radii[i];
swap(mxRad1, mxRad);
}else if(radii[i] > mxRad1) mxRad1 = radii[i];
}
if(t+1 >= 3){
mxDist = max(mxDist, mxRad1 + mxRad + L * 2);
}
return mxDist;
}
// int A[] = {0, 8, 2, 5, 5, 1, 1, 10};
// int B[] = {8, 2, 7, 11, 1, 3, 9, 6};
// int T[] = {4, 2, 4, 3, 7, 1, 5, 3};
// int main(){
// int ans = travelTime(12, 8, 2, A, B, T);
// cout << ans << '\n';
// return 0;
// }
