Description

【题意】
给定一棵基环树，树中包含 $n$ 个结点(编号 $1 \cdots n$ )和 $n$ 条无向边（保证联通），每条边都有一个权值。现在请你找到树中的一条最长路径。换句话说，要找到一条路径，使得路径两端点的距离最远。
注意:路径中可以只包含一个点。

【输入格式】
第一行包含整数 $n$ ，表示点的个数。
接下来 $n$ 行，每行包含三个整数 $a_i,b_i,c_i$ ，表示点 $a_i$ 和 $b_i$ 之间存在一条权值为ci 的边（$1 \le n \le 10^4，-10^5 \le c_i \le 10^5$）

【输出格式】
输出一个整数，表示树的最长路径的长度。

【样例输入】
6
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
2 5 1

【样例输出】
29

Hint

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e4+10;
struct edge {int x,y,w,pre;}a[N<<1];int alen,last[N];
void add(int x,int y,int w){alen++;a[alen]=edge{x,y,w,last[x]};last[x]=alen;}
int n,cn,cv[N],cw[N],tsp,dfn[N],v[N],pre[N];
LL ans,d[N],A[N],B[N],C[N],D[N];
void findc(int x,int kk)
{
dfn[x]=++tsp;
for(int k=last[x];k;k=a[k].pre)if(k!=(kk^1))
{
int y=a[k].y;
if(!dfn[y])
{
pre[y]=k;
findc(y,k);
}
else if(dfn[x]<dfn[y])
{
cn=0;
for(int z=y;z!=x;z=a[pre[z]].x)
{
++cn;cv[cn]=z;cw[cn]=a[pre[z]].w;
v[z]=1;
}
++cn;cv[cn]=x;cw[cn]=a[k].w;
v[x]=1;
}
}
}
void dp(int x,int kk)
{
v[x]=1;
for(int k=last[x];k;k=a[k].pre)if(k!=(kk^1))
{
int y=a[k].y,w=a[k].w;
if(!v[y])
{
dp(y,k);
ans=max(ans,d[x]+d[y]+w);
d[x]=max(d[x],d[y]+w);
}
}
}
int main()
{
scanf("%d",&n);
alen=1;memset(last,0,sizeof(last));
for(int i=1,x,y,w; i<=n; i++)
{
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
add(y,x,w);
}
tsp=0;memset(dfn&#44;0&#44;sizeof(dfn));
memset(v&#44;0&#44;sizeof(v));
findc(1&#44;0);//深搜找环

ans=0;for(int i=1; i&lt;=cn; i++)dp(cv[i]&#44;0);//深搜求直径ans

LL sum=0&#44;mx=0&#44;cw1n=cw[cn];
A[0]=B[0]=0;
for(int i=1; i&lt;=cn; i++) //求前缀
{
	sum+=cw[i-1];if(i==1)sum=0;
	A[i]=max(A[i-1]&#44;sum+d[cv[i]]);
	B[i]=max(B[i-1]&#44;mx+d[cv[i]]+sum);
	mx=max(mx&#44;d[cv[i]]-sum);
}

sum=mx=0;
C[cn+1]=D[cn+1]=0;
for(int i=cn; i&gt;=1; i--) //求后缀
{ 
	sum+=cw[i];if(i==cn) sum=0;
	C[i]=max(C[i+1]&#44;sum+d[cv[i]]);
	D[i]=max(D[i+1]&#44;mx+d[cv[i]]+sum);
	mx=max(mx&#44;d[cv[i]]-sum);
}

for(int i=1; i&lt;cn; i++) //拼凑答案，断i和i+1之间的边 
	ans=max( {ans&#44;B[i]&#44;D[i+1]&#44;A[i]+C[i+1]+cw1n} );
ans=max(ans&#44;B[cn]);//断1和n之间的边

printf("%lld\n"&#44;ans);
return 0;

}

</p>