1-D29 基环树 P1399 [NOI2013] 快餐店

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+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 d[N],A[N],B[N],C[N],D[N],ans;
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,kk);
		} 
		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,kk);
			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,0,sizeof(dfn));
	memset(v,0,sizeof(v));
	findc(1,0);//深搜找环
	ans=0;for(int i=1; i<=cn; i++)dp(cv[i],0);//深搜求直径ans1
	
	LL sum,mx;
	sum=mx=0;
	for(int i=1; i<=cn; i++) //求前缀
	{
		sum+=cw[i-1];if(i==1)sum=0;
		A[i]=max(A[i-1],sum+d[cv[i]]);
		B[i]=max(B[i-1],mx+d[cv[i]]+sum);
		mx=max(mx,d[cv[i]]-sum);
	}
	
	sum=mx=0;
	for(int i=cn; i>=1; --i) //求后缀
	{ 
		sum+=cw[i];if(i==cn) sum=0;
		C[i]=max(C[i+1],sum+d[cv[i]]);
		D[i]=max(D[i+1],mx+d[cv[i]]+sum);
		mx=max(mx,d[cv[i]]-sum);
	}
	LL cw1n=cw[cn],t=(LL)1<<60;
	for(int i=1; i<cn; ++i) //拼凑答案，断i和i+1之间的边 
	{
		t=min(t, max({B[i],D[i+1], A[i]+C[i+1]+cw1n}));
	}
	t=min(t,B[cn]);//断1和n之间的边
	ans=max(ans,t);
	printf("%.1lf",ans/2.0);
	return 0;
}