|

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];
void Lian(int x,int y,int z)
{
tot++;
edge[tot].to=y;
edge[tot].val=z;
}
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;
{
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)
{
{
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
?
?
?
?