/*
由于边是n那么图形肯定是一个环带一些链
我们断边肯定断在环上
那么最大的边权只可能有两种情况,一种是在链上
或者说是经过环的一条链
我们可以用染色法dfs去找到环,这一步如果不理解就把这个算法放进板子里要用的时候直接copy
然后对环上的点我们需要找到这个点往下延伸的最长链
在这个过程顺便用dp把当前点所在树的最长直径算了
所有最长直径取max扔进ans变量里
然后我们再去算经过环的最长链,我们去枚举一下断的是什么边
我们可以发现假设断的是x边,那么这边往前的一个点的最长链+前缀路径,加上后缀一个点的最长链加上后缀路径
或者是前缀两个点最长路径相加再加上这两个点间的路径,或者是后缀两个点
这样就可以算经过环的最长链
这部分维护两个前缀和两个后缀就可以解决
两者取max就是答案了
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
const int M=2*N;
int h[N], e[M], ne[M],w[M],idx;
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int n;
int co[N];
int vis[N];
int s2[N];
vector<int> gis;
int lastlast=-1;
int pre[N],pre1[N];
int suf[N],suf1[N];
int dfs(int u,int fa)//染色法找环
{
co[u]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
if(co[j]==0)
{
int w=dfs(j,u);
if(w==1)
{
gis.push_back(u);
vis[u]=true;
if(u==lastlast) return -1;
else return 1;
}
else if(w==-1)return -1;
}
else
{
if(co[j]==1)
{
lastlast=j;
gis.push_back(u);
vis[u]=true;
return 1;
}
}
}
co[u]=2;
return 0;
}
int ai[N];
int si[N];
int dp[N];
int dp1[N];
int ans=0;
void dfs1(int u,int fa)//算环上点的最长链,和这个点为根构成树的最长直径计入ans
{
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
if(vis[j]) continue;
dfs1(j,u);
dp1[u]=max(dp1[u],dp[u]+dp[j]+w[i]);
dp[u]=max(dp[u],dp[j]+w[i]);
}
ans=max(ans,dp1[u]);
}
int suff[N];
signed main()
{
memset(h, -1, sizeof h);
cin >> n;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin >> a>>b>>c;
add(a,b,c);
add(b,a,c);
}
dfs(1,-1);
int cnt=0;
for(auto u:gis)
{
ai[++cnt]=u;
dfs1(u,-1);
}
ai[++cnt]=ai[1];
for(int i=2;i<=cnt;i++)
{
int last=i-1;
for(int j=h[ai[i]];j!=-1;j=ne[j])
{
int k=e[j];
if(k==ai[last])
{
si[i]=w[j];
break;
}
}
//cout << si[i]<<" ";
}
for(int i=cnt-1;i>=1;i--)
{
s2[i]=si[i+1];
}
int mx=-1e18;
for(int i=1;i<cnt;i++)
{
si[i]+=si[i-1];
pre[i]=max(pre[i-1],dp[ai[i]]+si[i]);
pre1[i]=max(pre1[i-1],dp[ai[i]]+mx+si[i]);
mx=max(dp[ai[i]]-si[i],mx);
}
mx=-1e18;
for(int i=cnt-1;i>=1;i--)
{
s2[i]+=s2[i+1];
suf[i]=max(suf[i+1],dp[ai[i]]+s2[i]);
suf1[i]=max(suf1[i+1],dp[ai[i]]+s2[i]+mx);
mx=max(mx,dp[ai[i]]-s2[i]);
}
int res=1e18;
for(int i=1;i<=cnt;i++)
{
int len=-1e18;
len=max({pre[i-1]+suf[i],suf1[i],pre1[i-1]});
//cout << len<<"\n";
//cout << pre[i-1]+suf[i]<<" "<<suf1[i]<<" "<<pre1[i-1]<<"\n";
res=min(res,len);
}
//cout << ans<<" "<<res<<"\n";
ans=max(ans,res);
cout << ans<<"\n";
}
宝宝好厉害