General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
89297365 Practice:
luogu_bot2
835F - 34 GNU C++11 Accepted 124 ms 33512 KB 2020-08-08 04:24:42 2020-08-08 04:24:42
 
 
→ Source
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
const ll Inf=0x3f3f3f3f3f3f3f3f;
int n,x,y,z,cnt,tot,head[maxn],vis[maxn];
ll res,r[maxn],l[maxn],l0[maxn],r0[maxn],sum[maxn],ans1,ans2=Inf,f[maxn],cir[maxn];
struct Edge{
	int to,next,w;
}e[maxn<<1];
void add(int u,int v,int w) {
	e[++cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int fnd(int u,int fa=-1) {
	if(vis[u]) return u;
	vis[u]=-1;
	for(int i=head[u];i;i=e[i].next) {
		int v=e[i].to;
		if(v!=fa) {
			res=fnd(v,u);
			if(res) return cir[++tot]=u,sum[tot]=e[i].w,vis[u]=1,res==u?0:res;
		}
	}
	return 0;
}
void dfs(int u,int fa=-1) {
	for(int i=head[u];i;i=e[i].next) {
		int v=e[i].to;
		if(vis[v]!=1&&v!=fa) {
			dfs(v,u);
			ans1=max(ans1,f[u]+f[v]+e[i].w);
			f[u]=max(f[u],f[v]+e[i].w);
		}
	}
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	fnd(1);
	sum[0]=0;
	for(int i=1;i<=tot;i++) {
		dfs(cir[i]);
		sum[i]+=sum[i-1];
	}
	res=l[0]=l0[0]=-Inf;
	for(int i=1;i<=tot;i++) {
		l0[i]=max(l0[i-1],f[cir[i]]+sum[i]+res);
		l[i]=max(l[i-1],f[cir[i]]+sum[i]);
		res=max(res,f[cir[i]]-sum[i]);	
	}
	res=r[tot+1],r0[tot+1]=-Inf;
	for(int i=tot;i>=1;i--) {
		r0[i]=max(r0[i+1],f[cir[i]]-sum[i]+res);
		r[i]=max(r[i+1],f[cir[i]]+sum[tot]-sum[i]);
		res=max(res,f[cir[i]]+sum[i]);
	}
	for(int i=1;i<=tot;i++) {
		ans2=min(ans2,max(l[i-1]+r[i],max(l0[i-1],r0[i])));
	}
	printf("%lld\n",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