思路：
给出的一棵树，只要找到两个距离最大的节点就可以了。两遍搜
#include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #include <vector> #include <iostream> using namespace std; int ans1,max1,ans2,max2; int n; const int maxn=100005; vector< pair<int,int> >vec[maxn]; int vis[maxn]; void dfs(int x,int num) { if(num>max1) { max1=num; ans1=x; } for(int i=0;i<vec[x].size();i++) { int v=vec[x][i].first,w=vec[x][i].second; //cout<<x<<" "<<v<<" "<<num<<endl; if(!vis[v]) { vis[v]=1; dfs(v,num+w); vis[v]=0; } } } void dfs2(int x,int num) { if(num>max2) { max2=num; ans2=x; } for(int i=0;i<vec[x].size();i++) { int v=vec[x][i].first,w=vec[x][i].second; if(!vis[v]) { vis[v]=1; dfs2(v,num+w); vis[v]=0; } } } int main() { scanf("%d",&n); for(int i=0;i<=n;i++) { vec[i].clear(); vis[i]=0; } ans1=0,max1=0,ans2=0,max2=0; for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); vec[--u].push_back( make_pair(--v,w) ); vec[v].push_back(make_pair(u,w) ); } vis[0]=1; dfs(0,0); memset(vis,0,sizeof(vis)); vis[ans1]=1; dfs2(ans1,0); printf("%d",(1+max2)*max2/2+max2*10); }
