#include "dreaming.h" #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; vector<array<int, 2>> adj[N], nadj[N]; int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for (int i = 0; i < M; ++i) { int u = A[i], v = B[i], w = T[i]; ++u, ++v; adj[u].push_back({v, w}); adj[v].push_back({u, w}); nadj[u].push_back({v, w}); nadj[v].push_back({u, w}); } vector<int> add; vector<bool> used(N + 1, false); for (int i = 1; i <= N; ++i) { if (used[i]) continue; map<int, int> mp; function<void(int)> dfs1 = [&](int u) { used[u] = true; for (auto &[v, w] : adj[u]) { if (used[v]) continue; mp[v] = mp[u] + w; dfs1(v); } }; dfs1(i); int node = 0; for (auto &[u, d] : mp) { if (d > mp[node]) node = u; } for (auto &[u, d] : mp) used[u] = false; mp[node] = 0; dfs1(node); int vertex = 0; for (auto &[u, d] : mp) { if (d > mp[vertex]) vertex = u; } for (auto &[u, d] : mp) used[u] = false; map<int, int> mp1; function<void(int)> dfs2 = [&](int u) { used[u] = true; for (auto &[v, w] : adj[u]) { if (used[v]) continue; mp1[v] = mp1[u] + w; dfs2(v); } }; dfs2(vertex); // cout << vertex << '\n'; // for (auto &[u, d] : mp1) cout << u << ' ' << d << '\n'; // cout << '\n'; // continue; map<int, int> mx; for (auto &[u, d] : mp1) { mx[u] = max(d, mp[u]); } // for (auto &[u, d] : mx) cout << u << ' ' << d << '\n'; // cout << '\n'; // continue; int mn = 0; mx[mn] = 1e9; for (auto &[u, d] : mx) { if (d <= mx[mn]) mn = u; // cout << u << ' ' << mx[u] << ' '; } // cout << '\n'; if (adj[i].empty()) mn = i; add.push_back(mn); } for (int i = 0; i < size(add) - 1; ++i) { int u = add[i], v = add[i + 1]; nadj[u].push_back({v, L}); nadj[v].push_back({u, L}); } for (int i = 1; i <= N; ++i) used[i] = false; vector<int> d(N + 1, 0); function<void(int)> dfs = [&](int u) { used[u] = true; for (auto &[v, w] : nadj[u]) { if (used[v]) continue; d[v] = d[u] + w; dfs(v); } }; dfs(1); int node = 0; for (int i = 1; i <= N; ++i) { if (d[i] >= d[node]) node = i; } for (int i = 1; i <= N; ++i) used[i] = false; d[node] = 0; dfs(node); int vertex = 0; for (int i = 1; i <= N; ++i) { if (d[i] >= d[vertex]) vertex = i; } for (int i = 1; i <= N; ++i) used[i] = false; vector<int> d1(N + 1, 0); function<void(int)> dfs2 = [&](int u) { used[u] = true; for (auto &[v, w] : nadj[u]) { if (used[v]) continue; d1[v] = d1[u] + w; dfs2(v); } }; dfs2(vertex); return d1[node]; }