General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
121772693 Practice:
luogu_bot2
835F - 34 GNU C++11 Accepted 124 ms 28940 KB 2021-07-09 05:23:12 2021-07-09 05:23:12
 
 
→ Source
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n;
struct node
{
	int to,nxt,val;
}edge[2*N];
int head[N],tot=0;
void Lian(int x,int y,int z)
{
	tot++;
	edge[tot].to=y;
	edge[tot].nxt=head[x];
	edge[tot].val=z;
	head[x]=tot;
}
int vis[N],c[N],t=0;
long long Fa,ans1,ans2,f[N],L[N],L0[N],R[N],R0[N],v[N];
int dfs1(int x,int fa)
{
	if(vis[x]) return x;
	vis[x]=1;
	for(int i=head[x];i;i=edge[i].nxt)
	{
		int y=edge[i].to;
		if(y==fa) continue;
		Fa=dfs1(y,x);
		if(Fa)
		{
			c[++t]=x,v[t]=edge[i].val,vis[x]=2;
			if(Fa==x) return 0;
			else return Fa;
		}
	}
	return 0;
}
void dfs2(int x,int fa)
{
	for(int i=head[x];i;i=edge[i].nxt)
	{
		int y=edge[i].to;
		if(vis[y]==2||y==fa) continue;
		dfs2(y,x);
		ans1=max(ans1,f[x]+f[y]+edge[i].val);
		f[x]=max(f[x],f[y]+edge[i].val);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		Lian(u,v,w);
		Lian(v,u,w);
	}
	dfs1(1,0);
	for(int i=1;i<=t;i++) v[i]+=v[i-1];
	for(int i=1;i<=t;i++) dfs2(c[i],0);
	Fa=L[0]=L0[0]=-1e18;
	for(int i=1;i<=t;i++)
	{ 
		L0[i]=max(L0[i-1],f[c[i]]+v[i]+Fa);
		L[i]=max(L[i-1],f[c[i]]+v[i]);
		Fa=max(Fa,f[c[i]]-v[i]);
	}
	Fa=R[t+1]=R0[t+1]=-1e18;
	for(int i=t;i>=1;i--)
	{
		R0[i]=max(R0[i+1],f[c[i]]-v[i]+Fa);
		R[i]=max(R[i+1],f[c[i]]+v[t]-v[i]);
		Fa=max(Fa,f[c[i]]+v[i]);
	}
	ans2=1e18;
	for(int i=1;i<=t;i++) ans2=min(ans2,max(L[i-1]+R[i],max(L0[i-1],R0[i])));
	printf("%lld",max(ans1,ans2));
	return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details