#include <bits/stdc++.h> #include "dreaming.h" using namespace std; using ll = long long; using P = pair<int, int>; #define all(x) x.begin(), x.end() #define rep(i, l, n) for (int i = l; i < (n); ++i) #define sz(x) (int)x.size() const char nl = '\n'; const int mod = 1e9+7; const int N = 1e5+10; int vis[N], mx, s; P from[N]; vector<P> g[N]; void dfs(int nd, int dis, int p) { if (dis > mx)mx = dis, s = nd; for (auto [i, w]: g[nd]) if (i != p)dfs(i, dis+w, nd); } void yol(int nd, int p, int dis) { from[nd] = {p, dis}; for (auto [i, w]: g[nd]) if (i != p)yol(i, nd, dis+w); } P calc(int nd) { mx = s = 0; dfs(nd, 0, nd); int a = s; mx = s = 0; dfs(a, 0, a); int b = s; yol(a, -1, 0); int c1 = nd, c2 = -1; while (from[b].first != -1) { if (from[b].second >= mx/2)c1 = b; else if (c2 == -1)c2 = b; b = from[b].first; } if (c2 == -1)c2 = nd; return {c1, c2}; } int travelTime(int n, int m, int l, int aa[], int ba[], int tt[]) { rep(i, 0, m) { //int a, b, t; cin >> a >> b >> t; g[aa[i]].push_back(P(ba[i], tt[i])); g[ba[i]].push_back(P(aa[i], tt[i])); } int a = 1, b = 2; if (n != 2) { rep(i, 0, n) if (sz(g[i]) == 0)b = i; rep(i, 0, n) if (sz(g[i]))a = i; } //cout << a << " " << b << nl; P x = calc(a); g[x.first].push_back({b, l}); g[b].push_back({x.first, l}); calc(x.first); int res = mx; g[x.first].pop_back(); g[b].pop_back(); g[x.second].push_back({b, l}); g[b].push_back({x.second, l}); calc(x.second); res = min(res, mx); return res; } //int32_t main() { //ios_base::sync_with_stdio(0); //cin.tie(0); //solve(); //return 0; //}