我是真的没看出来这是一棵树。。。
易得，答案一定是折返了的,然后对于每个中心找最长的三条链 l1 <= l2 <=l3 ans = max { l1 + l2 * 2 + l3 }
然后随便搞搞就没了
代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m; const int N=4e5+5,M=8e5+5; int hed[N],nxt[M],to[M],cnt;ll val[M]; void adde(int u,int v,ll w){ cnt++;to[cnt]=v,nxt[cnt]=hed[u],val[cnt]=w;hed[u]=cnt; } ll dep[N]; ll mxdep[N]; inline void dfs1(int x,int pre){ mxdep[x]=dep[x]; for(int i=hed[x];i;i=nxt[i]){ int v=to[i];if(v==pre)continue; dep[v]=dep[x]+val[i]; dfs1(v,x); mxdep[x]=max(mxdep[v],mxdep[x]); } } ll mx[N][7]; ll ans=0; inline void dfs2(int x,int pre,ll UP){ for(int i=hed[x];i;i=nxt[i]){ int v=to[i];if(v==pre)continue; mx[x][1]=mxdep[v]-dep[x]; sort(mx[x]+1,mx[x]+5); } for(int i=hed[x];i;i=nxt[i]){ int v=to[i];if(v==pre)continue; ll MX=mxdep[v]-dep[x]; if(MX==mx[x][4])MX=mx[x][3]; else MX=mx[x][4]; dfs2(v,x,max(MX,UP)+val[i]); } mx[x][1]=UP; sort(mx[x]+1,mx[x]+5); ans=max(ans,mx[x][4]+2*mx[x][3]+mx[x][2]); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v;ll w;scanf("%d%d%lld",&u,&v,&w); adde(u,v,w);adde(v,u,w); } dfs1(1,0); dfs2(1,0,0); printf("%lld\n",ans); }
