#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int travelTime(int node_count, int edge_count, int added_weight, int firsts[], int seconds[], int weights[]) {
vector<vector<pair<int, int>>> forest(node_count);
for (int edge = 0; edge < edge_count; edge++) {
forest[firsts[edge]].emplace_back(seconds[edge], weights[edge]);
forest[seconds[edge]].emplace_back(firsts[edge], weights[edge]);
}
vector<pair<int, int>> centroids;
vector<pair<int, int>> dp(node_count);
vector<bool> visited(node_count);
function<void(int, int)> inside_dfs = [&](int node, int parent) {
for (auto [child, weight]: forest[node]) {
if (child == parent) continue;
inside_dfs(child, node);
dp[node].first = max(dp[node].first, dp[child].first + weight);
}
};
function<void(int, int)> outside_dfs = [&](int node, int parent) {
pair<int, int> best = make_pair(dp[node].second, node), second_best = make_pair(0, 0);
for (auto [child, weight]: forest[node]) {
if (child == parent) continue;
pair<int, int> distance = make_pair(dp[child].first + weight, child);
if (distance > best) {
second_best = best;
best = distance;
}
else if (distance > second_best) {
second_best = distance;
}
}
for (auto [child, weight]: forest[node]) {
if (child == parent) continue;
if (best.second == child) {
dp[child].second = second_best.first + weight;
}
else {
dp[child].second = best.first + weight;
}
outside_dfs(child, node);
}
};
for (int node = 0; node < node_count; node++) {
if (visited[node]) continue;
vector<int> tree;
inside_dfs(node, -1);
outside_dfs(node, -1);
centroids.emplace_back(max(dp[node].first, dp[node].second), node);
function<void(int, int)> centroid_dfs = [&](int node, int parent) {
visited[node] = true;
centroids.back() = min(centroids.back(), make_pair(max(dp[node].first, dp[node].second), node));
for (auto [child, weight]: forest[node]) {
if (child == parent) continue;
centroid_dfs(child, node);
}
};
centroid_dfs(node, -1);
}
sort(centroids.begin(), centroids.end());
for (int index = 0; index < centroids.size() - 1; index++) {
int first = centroids[index].second, second = centroids.back().second;
forest[first].emplace_back(second, added_weight);
forest[second].emplace_back(first, added_weight);
}
fill(dp.begin(), dp.end(), make_pair(0, 0));
inside_dfs(centroids.back().second, -1);
outside_dfs(centroids.back().second, -1);
int diameter = 0;
function<void(int, int)> diameter_dfs = [&](int node, int parent) {
int best = dp[node].second, second_best = 0;
for (auto [child, weight]: forest[node]) {
if (child == parent) continue;
int distance = dp[child].first + weight;
if (distance > best) {
second_best = best;
best = distance;
}
else if (distance > second_best) {
second_best = distance;
}
diameter_dfs(child, node);
}
diameter = max(diameter, best + second_best);
};
diameter_dfs(centroids.back().second, -1);
return diameter;
}
