求出树上最远的两个点的距离
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 #define maxn 10100 5 6 struct edge 7 { 8 int v,w; 9 edge(int vv,int ww):v(vv),w(ww){} 10 }; 11 12 int n; 13 int dist[maxn],max_len,endd; 14 vector<vector<edge> >G; 15 16 void dfs(int u,int father,int len) 17 { 18 if(len>max_len) 19 max_len=len,endd=u; 20 for(int i=0;i<G[u].size();i++) 21 { 22 int v=G[u][i].v, 23 w=G[u][i].w; 24 if(v==father) continue; 25 dist[v]=max(dist[v],len+w); 26 dfs(v,u,len+w); 27 } 28 } 29 int main() 30 { 31 int u,v,w; 32 while(~scanf("%d",&n)) 33 { 34 G.clear(); 35 G.resize(n+2); 36 for(int i=1;i<n;i++) 37 { 38 scanf("%d%d%d",&u,&v,&w); 39 G[u].push_back(edge(v,w)); 40 G[v].push_back(edge(u,w)); 41 } 42 memset(dist,0,sizeof dist); 43 max_len=0; 44 dfs(1,-1,0); 45 dfs(endd,-1,0); 46 int ans=0; 47 for(int i=1;i<=n;i++) 48 { 49 ans=max(ans,dist[i]); 50 } 51 int tt=0; 52 for(int i=1;i<=ans;i++) 53 { 54 tt+=(10+i); 55 56 } 57 printf("%d ",tt); 58 } 59 return 0; 60 }
原题链接:http://lx.lanqiao.cn/problem.page?gpid=T32
参考博客:https://blog.csdn.net/buctyyzyn/article/details/44886697