#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> to, sz;
//ez union find
int find(int x){
if(x==to[x]) return x;
return to[x] = find(to[x]);
}
void unite(int u, int v){
int x = find(u);
int y = find(v);
if (x == y)
return;
if (sz[x] < sz[y])swap(x, y);
sz[x]+=sz[y];
to[y] = x;
}
bool same(int u, int v){
return find(u) == find(v);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
//first step: find optimal point in which to add the new edge (for each component)
//this can be done by starting from the bottom and finding the maximum from each side of the tree
//we need to recursively find the nodes that only have one (zero?!) (unvisited) edge(s)
//can probably be done with good time complexity but idk (i think it could become O(NlogN)? probably N squared done lazily)
//from the input data we can easily create a vector<>[] representation as follows
vector<pair<int, int>> node[N]; //node[a] = {b, w}
vector<pair<int, int>> nodec[N]; //node[a] = {b, w}
vector<pair<int, int>> noded[N]; //node[a] = {b, w}
vector<tuple<int, int, int>> edges;
int comp[N];
bool visited[N];
//epic dfs lambda
function<void(int, int)> dfs = [&node, &comp, &dfs, &visited](int i, int n){
if(visited[i])return;
visited[i] = true;
comp[i] = n;
for(auto e : node[i])dfs(e.first, n);
};
for(int i = 0; i < M; i++){
node[A[i]].push_back({B[i], T[i]});
node[B[i]].push_back({A[i], T[i]});
nodec[A[i]].push_back({B[i], T[i]});
nodec[B[i]].push_back({A[i], T[i]});
noded[A[i]].push_back({B[i], T[i]});
noded[B[i]].push_back({A[i], T[i]});//it sets it 3 times because i was too lazy to let it copy later on in the code
edges.push_back(make_tuple(A[i], B[i], T[i]));
edges.push_back(make_tuple(B[i], A[i], T[i]));//for kruskal
}
//dfs to find the separate components
for(int i = 0; i < N; i++)dfs(i, i);
//next, we need to recursively find the tree "endings"
//we just need to check if the number of edges coming in is 0...
//we can probably do this for the whole tree with help from some array
/*int numin[N];
for(int i = 0; i < N; i++)numin[i] = 0;
for(int i = 0; i < N; i++){
for(auto e : node[i]){
numin[e.first]++;
}
}*/
vector<int> ord;
while(true){
for(int i = 0; i < N; i++){
if(nodec[i].size() == 1){
int il = 0;
for (auto it : nodec[nodec[i][0].first]) {
if(it.first==i)nodec[nodec[i][0].first].erase(nodec[nodec[i][0].first].begin() + il);
il++;
}
ord.push_back(i);
if(ord.size()==N)goto el;
}
}
}
el:
vector<int> maxer(N), fin(N, -1);
for(int i = 0; i < N; i++){
int t = ord[i];
if(noded[t].size() == 1){
if((maxer[t] + noded[t][0].second) > maxer[noded[t][0].first]){
maxer[noded[t][0].first] = maxer[t] + noded[t][0].second;
fin[comp[noded[t][0].first]] = noded[t][0].first;
}
int il = 0;
for (auto it : noded[noded[t][0].first]) {
if(it.first==t){
noded[noded[t][0].first].erase(noded[noded[t][0].first].begin() + il);
}
il++;
}
}
}
//ideally, the algorithm should be optimized to a better time complexity (finding the best vertex to connect can probably be done faster with the same idea)
//for it to work with the whole input, the different slots should be permutated (maybe??? or Mst recalced every time???????)
//let's complete (inaccurately) for M = N-2
//join the two ideal vertices and then calculate the Mst
int finq = -1;
for(int i = 0; i < N; i++){
if(finq==-1){
if(fin[i]!=-1)finq = fin[i];
}else{
//assuming that M is equal to N-2
edges.push_back(make_tuple(L, i, finq));
edges.push_back(make_tuple(L, finq, i));
}
}
//we now should theoretically have a fully connected graph of which we should find the maximum spanning tree
//the solution to the problem will be equal to the final maximum spanning tree
//we can easily implement the maximum spanning tree using a union-find structure
sort(edges.rbegin(), edges.rend());
to.resize(N);
sz.resize(N, 0);
iota(to.begin(), to.end(), 0);
int tot = 0;
for(auto e : edges){
if(!same(get<1>(e), get<2>(e))){
unite(get<1>(e), get<2>(e));
tot+=get<0>(e);
}
}
return tot;
}
