//Dreaming #include<bits/stdc++.h> #include "dreaming.h" using namespace std; constexpr int MAX_N=1e5+9, LOG=18, INF=1e9; vector<pair<int, int>> drzewo[MAX_N]; bool odw[MAX_N]; int jump[MAX_N][LOG], odl[MAX_N], korzen[MAX_N], gl[MAX_N], maksodl, a, minodl=INF; pair<int, int> sred[MAX_N], maks[MAX_N]; void dfs(int w, int ojc=0){ jump[w][0]=ojc; gl[w]=gl[ojc]+1; for (int i=1; i<LOG; i++) jump[w][i]=jump[jump[w][i-1]][i-1]; odw[w]=true; for (auto [new_w, c]:drzewo[w]){ if (!odw[new_w]){ odl[new_w]=odl[w]+c; if (maksodl<odl[new_w]) maksodl=odl[new_w], a=new_w; dfs(new_w, w); } } } void dfs2(int w, int akt=0, int ojc=0){ if (akt>maksodl) maksodl=akt, a=w; for (auto [new_w, c]:drzewo[w]) if (new_w!=ojc) dfs2(new_w, akt+c, w); } int lca(int x, int y){ if (gl[x]<gl[y]) swap(x, y); for (int i=LOG-1; i>=0; i--) if ((gl[x]-gl[y])>=(1<<i)) x=jump[x][i]; if (x==y) return x; for (int i=LOG-1; i>=0; i--) if (jump[x][i]!=jump[y][i]) x=jump[x][i], y=jump[y][i]; return jump[x][0]; } void znajdz_korzen(int w, pair<int, int> x, int ojc=0){ int nowa=max(odl[w]+odl[x.first]-2*odl[lca(w, x.first)], odl[w]+odl[x.second]-2*odl[lca(w, x.second)]); if (nowa<minodl) minodl=nowa, a=w; for (auto [new_w, c]:drzewo[w]) if (new_w!=ojc) znajdz_korzen(new_w, x, w); } void ustaw_korzen(int w, int k, int ojc=0){ korzen[w]=k; for (auto [new_w, c]:drzewo[w]) if(new_w!=ojc) ustaw_korzen(new_w, k, w); } int travelTime(int N, int M, int L, int A[], int B[], int T[]){ for (int i=0; i<M; i++) drzewo[A[i]+1].push_back({B[i]+1, T[i]}), drzewo[B[i]+1].push_back({A[i]+1, T[i]}); /* int b, c; for (int i=0; i<M; i++) cin >> a >> b >> c, drzewo[a+1].push_back({b+1, c}), drzewo[b+1].push_back({a+1, c}); */ vector<int> spojne; int wyn=0; for (int i=1; i<=N; i++){ if (!odw[i]){ maksodl=0, a=i; dfs(i); sred[i].first=a; maksodl=0, a=i; dfs2(sred[i].first); sred[i].second=a; minodl=INF, a=i; znajdz_korzen(i, sred[i]); ustaw_korzen(i, a); sred[a]=sred[i]; wyn=max(wyn, odl[sred[a].first]+odl[sred[a].second]-2*odl[lca(sred[a].first, sred[a].second)]); int pom=max(odl[sred[a].first]+odl[a]-2*odl[lca(a, sred[a].first)], maks[a].second=odl[sred[a].second]+odl[a]-2*odl[lca(a, sred[a].second)]); spojne.push_back(pom); } } sort(spojne.begin(), spojne.end(), greater<int>()); if (spojne.size()>=3) wyn=max(wyn, spojne[1]+2*L+spojne[2]); if (spojne.size()>=2) wyn=max(wyn, spojne[0]+spojne[1]+L); return wyn; } /* int main(){ int n, m, l; cin >> n >> m >> l; cout << travelTime(n, m, l); } */