路径可以分为两部分：跨过环 和 在树内部。
要删除一条边，使图形变为一棵树，那么只能删去环上的一条边，因此，我们无法改变第二部分的路径，但是可以改变第一部分。
对于第二部分可以通过两次搜索或者树形动态规划解决。
对于第一部分，考虑枚举删去环上的一条边。但是发现仍然不太方便处理，因为不好维护环上的信息。仍然考虑剖环成链。
假设环的大小为$k$，从剖点开始依次将所有点标号1到$k$。
当一条边被删除后，第二部分可能成为答案的情况有两种：
- 不跨过剖点和被删边的路径
- 跨过剖点但不经过被删边的路径
因此考虑维护一些数组。
- 在$1, 2, \cdots, i$及其所在的树中的最长路。
- 从$1$开始，到$1, 2, \cdots, i$及其所在的树中的最长路。
- 在$k, k - 1, \cdots, i$及其所在的树中的最长路。
- 从$k$开始，到$k, k - 1, \cdots, i$及其所在的树中的最长路。
这四个部分都可以线性预处理出来。然后枚举删掉的环边就能统计第一部分的答案。
Code
/**
* Codeforces
* Problem#835F
* Accepted
* Time: 155ms
* Memory: 27100k
*/
#include <bits/stdc++.h>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean; typedef class Edge {
public:
int ed, nx, w; Edge(int ed = , int nx = , int w = ):ed(ed), nx(nx), w(w) { }
}Edge; typedef class MapManager {
public:
int ce;
int* h;
Edge* es; MapManager() { }
MapManager(int n, int m):ce(-) {
h = new int[(n + )];
es = new Edge[(m + )];
memset(h, -, sizeof(int) * (n + ));
} void addEdge(int u, int v, int w) {
es[++ce] = Edge(v, h[u], w);
h[u] = ce;
} Edge& operator [] (int pos) {
return es[pos];
}
}MapManager; #define ll long long const signed ll llf = (signed ll) ((~0ull) >> ); int n;
int ccir, cc;
MapManager g;
stack<int> s;
boolean *vis, *icir;
int *cir, *nw;
ll *ap[], *cp[], *dep, *dis; inline void init() {
scanf("%d", &n);
vis = new boolean[(n + )];
icir = new boolean[(n + )];
cir = new int[(n + )];
nw = new int[(n + )];
dep = new ll[(n + )];
dis = new ll[(n + )];
for (int i = ; i < ; i++) {
ap[i] = new ll[(n + )];
cp[i] = new ll[(n + )];
}
g = MapManager(n, n << );
memset(vis, false, sizeof(boolean) * (n + ));
memset(icir, false, sizeof(boolean) * (n + ));
for (int i = , u, v, w; i <= n; i++) {
scanf("%d%d%d", &u, &v, &w);
g.addEdge(u, v, w);
g.addEdge(v, u, w);
}
} boolean getLoop(int p, int fa) {
if (vis[p]) {
ccir = ;
int cur = ;
do {
cur = s.top();
s.pop();
icir[cur] = true;
cir[ccir++] = cur;
cc = ccir - ;
} while (cur != p);
return true;
}
vis[p] = true;
s.push(p);
for (int i = g.h[p]; ~i; i = g[i].nx) {
int e = g[i].ed;
if (e == fa) continue;
if (getLoop(e, p)) {
if (icir[p]) {
nw[cc] = g[i].w;
cc = (cc + ) % ccir;
}
return true;
}
}
s.pop();
return false;
} void dfs(int p, int fa, ll dep, int& fn, ll& fd) {
if (dep > fd)
fd = dep, fn = p;
for (int i = g.h[p]; ~i; i = g[i].nx) {
int e = g[i].ed;
if (e == fa || icir[e]) continue;
dfs(e, p, dep + g[i].w, fn, fd);
}
} inline void solve() {
getLoop(, );
ll fixedd = ;
// for (int i = 0; i < ccir; i++)
// cerr << cir[i] << " ";
// cerr << endl;
// for (int i = 0; i < ccir; i++)
// cerr << nw[i] << " ";
// cerr << endl;
for (int i = , fn, fbn; i < ccir; i++) {
fn = -, dep[i] = ;
dep[i] = , dfs(cir[i], , , fn, dep[i]);
if (~fn)
icir[cir[i]] = false, dfs(fn, , , fbn, fixedd), icir[cir[i]] = true;
}
dis[] = ;
for (int i = ; i < ccir; i++)
dis[i] = nw[i - ];
for (int i = ; i < ccir; i++)
dis[i] += dis[i - ];
ll mi = dep[];
ap[][] = -llf, cp[][] = dep[];
for (int i = ; i < ccir; i++) {
ap[][i] = max(ap[][i - ], dep[i] + dis[i] + mi);
mi = max(mi, dep[i] - dis[i]);
cp[][i] = max(cp[][i - ], dep[i] + dis[i]);
}
mi = dep[ccir - ] + dis[ccir - ];
ap[][ccir - ] = -llf, cp[][ccir - ] = dep[ccir - ];
for (int i = ccir - ; ~i; i--) {
ap[][i] = max(ap[][i + ], dep[i] - dis[i] + mi);
mi = max(mi, dep[i] + dis[i]);
cp[][i] = max(cp[][i + ], dep[i] + dis[ccir - ] - dis[i]);
}
ll ans = ap[][ccir - ];
for (int i = ; i < ccir - ; i++)
ans = min(max(max(ap[][i], ap[][i + ]), cp[][i] + cp[][i + ] + nw[ccir - ]), ans);
printf(Auto, max(ans, fixedd));
} int main() {
init();
solve();
return ;
}