复习一下树的直径，多次dfs求解
#include<bits/stdc++.h> using namespace std; int n,m,a,b,ne,c,tpo=1,tp=1,head[405000]; long long ans,d[205000][2],dl[205000]; struct node{int nxt,v;long long dis;}eg[405000]; void adde(int u,int v,int val) {eg[++ne].v=v;eg[ne].dis=val;eg[ne].nxt=head[u];head[u]=ne;} void dfs(int u,int fa) { for(int i=head[u];i;i=eg[i].nxt) if(eg[i].v!=fa){dl[eg[i].v]=dl[u]+eg[i].dis;dfs(eg[i].v,u);} } void dfs2(int u,int fa,int tag) { for(int i=head[u];i;i=eg[i].nxt) if(eg[i].v!=fa){d[eg[i].v][tag]=d[u][tag]+eg[i].dis;dfs2(eg[i].v,u,tag);} } int main() { cin>>n>>m; for(int i=1;i<=m;i++) {cin>>a>>b>>c;adde(a,b,c);adde(b,a,c);} dfs(1,0); for(int i=2;i<=n;i++)if(dl[i]>dl[tp])tp=i; dl[tp]=0;dfs(tp,0); for(int i=2;i<=n;i++)if(dl[i]>dl[tpo])tpo=i; dfs2(tp,0,0);dfs2(tpo,0,1); for(int i=1;i<=n;i++)ans=max(min(d[i][1],d[i][0]),ans); cout<<ans+dl[tpo]; }