\(>Codeforces\space835 F. Roads in the Kingdom<\)
题目大意 : 给你一棵 \(n\) 个点构成的树基环树，你需要删掉一条环边，使其变成一颗树，并最小化删掉环边后的树的直径。
\(n \leq 2 \times 10^5\) 树的边权 $ \leq 10^9 $
解题思路 :
考虑最终树的直径可能由两部分组成，答案是其中的最大值
第一种就是外向树内的直径的最大值，这个只需要随便\(dp\)一下即可，这里不过多讨论
第二种情况树的直径经过原来的环，必然是环上的一段加上两端对应的外向树的 \(maxdep\)
设 \(l_i\) 为将环展开后环上第 \(i\) 个点到环左端点的距离，\(dep_i\) 为 环上第 \(i\) 个点对应的外向树的最大深度
设选取的环的左端点为 \(x\) 右端点为 \(y\) ，那么经过环上 \(x \rightarrow y\) 一段的树的直径就是可以表示为
\(l_y - l_x + dep_x + dep_y\)
问题自此转化为对于每一种把环展开的方式，求 \(\max(l_y - l_x + dep_x + dep_y)\)
即 \(\max(l_y + dep_y) - \min(l_x - dep_x) \ y \neq x\) 用两个\(set\) 分别维护即可
/*program by mangoyang*/
#include<bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int f = 0, ch = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + Qch - 48;
if(f) x = -x;
}
#define int ll
#define N (600005)
int a[N], b[N], head[N], nxt[N], cnt;
int st[N], ct[N], vis[N], success;
int g[N], dep[N], c[N], s[N], tot, top, n;
struct Node{
int val, id;
bool operator < (const Node &A) const{ return val < A.val; }
};
multiset<Node> s1, s2;
inline void add(int x, int y, int z){
a[++cnt] = y, b[cnt] = z; nxt[cnt] = head[x], head[x] = cnt;
}
inline void Getcircle(int u, int fa){
vis[u] = 1;
for(int p = head[u]; p; p = nxt[p]){
int v = a[p];
if(v == fa) continue;
if(!vis[v]){
st[++top] = v, ct[top] = b[p];
Getcircle(v, u);
}
else{
int pos = 1;
for(int i = 1; i <= top; i++)
if(st[i] == v){ pos = i; break; }
for(int i = pos; i <= top; i++)
c[++tot] = st[i], s[tot] = ct[i];
s[1] = b[p];
return (void) (success = 1);
}
if(success) return;
}
if(success) return; vis[u] = 0, top--;
}
inline int dfs(int u, int fa){
int mx = u;
for(int p = head[u]; p; p = nxt[p]){
int v = a[p];
if(v != fa && !vis[v]){
dep[v] = dep[u] + b[p];
int now = dfs(v, u);
if(dep[now] > dep[mx]) mx = now;
}
}
return mx;
}
inline int dfs2(int u, int fa, int dis, int t){
int res = dis;
for(int p = head[u]; p; p = nxt[p]){
int v = a[p];
if(v != fa){
if(vis[v] && t) continue;
if(!vis[v]){
int now = dfs2(v, u, dis + b[p], t);
if(now > res) res = now;
}
else{
int now = dfs2(v, u, dis + b[p], 1);
if(now > res) res = now;
}
}
}
return res;
}
inline ll calc1(){
multiset<Node>::iterator it2 = s2.begin();
int id = it2 -> id;
s1.erase(s1.find((Node){s[id] + g[id], id}));
multiset<Node>::iterator it1 = s1.end(); it1--;
int ans = it1 -> val - it2 -> val;
s1.insert((Node){s[id] + g[id], id});
return ans;
}
inline ll calc2(){
multiset<Node>::iterator it1 = s1.end(); it1--;
int id = it1 -> id;
s2.erase(s2.find((Node){s[id] - g[id], id}));
multiset<Node>::iterator it2 = s2.begin();
int ans = it1 -> val - it2 -> val;
s2.insert((Node){s[id] - g[id], id});
return ans;
}
inline ll calc(){ return max(calc1(), calc2()); }
main(){
read(n);
if(n <= 2) return puts("0"), 0;
for(int i = 1, x, y, z; i <= n; i++){
read(x), read(y), read(z);
add(x, y, z), add(y, x, z);
}
ll ans = 0;
st[++top] = 1, Getcircle(1, 0);
for(int i = 1; i <= n; i++) vis[i] = 0;
for(int i = 1; i <= tot; i++) vis[c[i]] = 1;
for(int i = 1; i <= tot; i++){
int mx = dfs(c[i], 0);
g[i] = dep[mx], ans = max(ans, g[i]);
ans = max(ans, dfs2(mx, 0, 0, mx == c[i] ? 1 : 0));
}
for(int i = 1; i <= tot; i++) g[i+tot] = g[i];
for(int i = 1; i <= tot; i++) s[i+tot] = s[i];
tot *= 2;
for(int i = 1; i <= tot; i++) s[i] += s[i-1];
for(int i = 1; i <= tot / 2; i++){
s1.insert((Node){s[i] + g[i], i});
s2.insert((Node){s[i] - g[i], i});
}
ll tmp = calc();
for(int i = 2; i <= tot / 2; i++){
int l = i, r = i + tot / 2 - 1;
s1.insert((Node){s[r] + g[r], r});
s2.insert((Node){s[r] - g[r], r});
s1.erase(s1.find((Node){s[l-1] + g[l-1], l - 1}));
s2.erase(s2.find((Node){s[l-1] - g[l-1], l - 1}));
tmp = min(tmp, calc());
}
cout << Max(ans, tmp);
return 0;
}