?
# | 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 |
#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; }
?
?
?
?