#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long int
#define endl '\n'
using namespace std;
class TreeNode {
public:
int id;
int group = -1;
vector<pair<TreeNode*, int>> neighbors = vector<pair<TreeNode*,int>>();
TreeNode(int i) {
id = i;
}
void addNeighbor(TreeNode* node, int l) {
neighbors.push_back(make_pair(node,l));
}
};
struct PathInfo {
vector<ll> path = vector<ll>();
TreeNode* lastNode;
int length = 0;
PathInfo(TreeNode* node) {
lastNode = node;
}
};
vector<TreeNode*> nodes;
ll findRadius(PathInfo* pathInfo) {
if (pathInfo->path.size() == 0) return 0;
if (pathInfo->path.size() == 1) return pathInfo->path[0];
// get the radius by going like
ll runningLength = 0;
ll maxLength = pathInfo->path[pathInfo->path.size()-1];
for (int i = 1; i < pathInfo->path.size(); i++) {
if (pathInfo->path[i] >= maxLength-(pathInfo->path[i])) {
return min(pathInfo->path[i], maxLength-(pathInfo->path[i-1]));
}
}
return 0;
}
// byproduct is that the group is labeled
PathInfo* farthestNode(TreeNode* parent, TreeNode* root, int group) {
root->group = group;
PathInfo* ans = nullptr;
for (pair<TreeNode*,int> neighbor : root->neighbors) {
if (parent != nullptr && neighbor.first->id == parent->id) continue;
PathInfo* farthest = farthestNode(root, neighbor.first, group);
farthest->length += neighbor.second;
farthest->path.push_back(farthest->length);
if (ans == nullptr || ans->length < farthest->length) {
ans = farthest;
}
}
if (ans == nullptr) {
return new PathInfo(root);
} else {
return ans;
}
}
vector<ll> radii, diameters;
ll numComponents = 0;
void findConnectedComponents(int N) {
for (int i = 0; i < N; i++) {
if (nodes[i]->group == -1) {
// dfs w that as a root node, then do stuff
// get tha radius GRAAAAH
PathInfo* farthest = farthestNode(nullptr,nodes[i],numComponents);
PathInfo* diameter = farthestNode(nullptr,farthest->lastNode,numComponents);
// cout << "diameter of " << i << endl;
// for (ll length : diameter->path) {
// cout << length << " ";
// }
// cout << endl;
radii.push_back(findRadius(diameter));
diameters.push_back(diameter->length);
numComponents++;
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
nodes = vector<TreeNode*>(N);
// make a node for each thing from 1-N
for (int i = 0; i < N; i++) {
TreeNode* thisNode = new TreeNode(i);
nodes[i] = thisNode;
}
for (int i = 0; i < M; i++) {
// a[i] is now a neighbor of b[i]
nodes[A[i]]->addNeighbor(nodes[B[i]], T[i]);
nodes[B[i]]->addNeighbor(nodes[A[i]], T[i]);
// opposite too
}
// ok now dfs to get the radius of each connected component
findConnectedComponents(N);
sort(radii.begin(),radii.end());
sort(diameters.begin(),diameters.end());
// for (ll cc : radii) {
// cout << cc << " ";
// }
// cout << endl;
if (radii.size() >= 3) {
return max(radii[numComponents-1]+radii[numComponents-2]+L, max(radii[numComponents-2]+radii[numComponents-3]+2*L, diameters[numComponents-1]));
} else if (radii.size() == 2) {
return max(radii[0] + radii[1] + L, diameters[1]);
} else {
return diameters[0];
}
}
//int main() {
// int n,m,l; cin >> n >> m >> l;
// int a[m],b[m],t[m];
// for (int i = 0; i < m; i++) {
// cin >> a[i] >> b[i] >> t[i];
// }
// cout << travelTime(n,m,l,a,b,t);
//}
