题面传送门 首先你可以把所有直径求出来然后暴力。 但是这道题可以把求树的直径的方法。 首先求出一条直径，把直径上的所有点点权减一。然后再求一遍，两次相减就是答案。 正确性显然。 代码实现:
#include<cstdio> #include<cstring> #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; int n,m,k,x,y,z,top[200039],st,t; long long ans,dp[200039],d[200039],now,tot,tots; struct yyy{int to,w,z,flag;}; struct ljb{ int head,h[200039]; yyy f[400039]; inline void add(int x,int y,int z){ f[++head]=(yyy){y,z,h[x],0}; h[x]=head; } }s; inline void dfs(int x,int last){ if(d[x]>d[ans]) ans=x; int cur=s.h[x]; yyy tmp; while(cur!=-1){ tmp=s.f[cur]; if(tmp.to!=last){ d[tmp.to]=d[x]+tmp.w; top[tmp.to]=cur; dfs(tmp.to,x); } cur=tmp.z; } } inline void dfs2(int x,int last){ int cur=s.h[x]; yyy tmp; while(cur!=-1){ tmp=s.f[cur]; if(tmp.to!=last){ dfs2(tmp.to,x); tots=max(tots,dp[x]+dp[tmp.to]+tmp.w); dp[x]=max(dp[x],dp[tmp.to]+tmp.w); } cur=tmp.z; } } int main(){ s.head=1; // freopen("road.in","r",stdin); // freopen("road.out","w",stdout); register int i; memset(s.h,-1,sizeof(s.h)); scanf("%d",&n); for(i=1;i<n;i++) scanf("%d%d%d",&x,&y,&z),s.add(x,y,z),s.add(y,x,z); dfs(1,1); memset(d,0,sizeof(d)); memset(top,0,sizeof(top)); st=ans; dfs(ans,ans);tot=d[ans]; printf("%lld\n",d[ans]); while(top[ans]) s.f[top[ans]].w--,s.f[top[ans]^1].w--,ans=s.f[top[ans]^1].to; dfs2(st,st); printf("%lld\n",tot-tots); }