输出一个整数，表示大臣J最多花费的路费是多少。
5 1 2 2 1 3 1 2 4 5 2 5 4
135
输出格式
大臣J从城市4到城市5要花费135的路费。
题意：该题目就是要求树的直径。
求树直径原理：
以任意点w开始，先做一次DFS（BFS），找到最远点v，然后以此点v，进行一次DFS（BFS），找到最远点u，u到v就是树的直径，记做d(u,v)。
证明：
1) 如果w 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点x使得w到x的距离更长，则与d(u,v)为直径冲突)
2）如果w不是直径上的点，则w到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了,所以v一定是直径的一个端点，所以从v进行DFS得到的一定是直径长度
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 #include <stack> 11 #include <map> 12 #include <sstream> 13 const int INF=0x3f3f3f3f; 14 typedef long long LL; 15 const int mod=1e9+7; 16 const int maxn=1e5+10; 17 using namespace std; 18 19 struct edge_node 20 { 21 int to; 22 int val; 23 int next; 24 }Edge[maxn*2]; 25 26 int Head[maxn]; 27 int tot; 28 int MAX;//最终为树的直径 29 int sum;//记录当前总花费 30 int st;//出发点 31 int vis[maxn];//标记数组 32 33 void Add_Edge(int u,int v,int val) 34 { 35 Edge[tot].to=v; 36 Edge[tot].val=val; 37 Edge[tot].next=Head[u]; 38 Head[u]=tot++; 39 } 40 41 void DFS(int n,int u)//n是总结点个数,u是出发点 42 { 43 vis[u]=1; 44 for(int i=Head[u];i!=-1;i=Edge[i].next) 45 { 46 int v=Edge[i].to; 47 if(vis[v]==0) 48 { 49 sum+=Edge[i].val; 50 if(sum>MAX) 51 { 52 MAX=sum; 53 st=v; 54 } 55 DFS(n,v); 56 sum-=Edge[i].val; 57 } 58 } 59 vis[u]=0; 60 } 61 62 int main() 63 { 64 int n; 65 scanf("%d",&n); 66 memset(Head,-1,sizeof(Head)); 67 tot=0; 68 for(int i=1;i<=n-1;i++) 69 { 70 int u,v,t; 71 scanf("%d %d %d",&u,&v,&t); 72 Add_Edge(u,v,t); 73 Add_Edge(v,u,t); 74 } 75 st=1;//st为出发点,初始为1 76 for(int i=1;i<=2;i++) 77 { 78 memset(vis,0,sizeof(vis)); 79 sum=0; 80 MAX=0; 81 DFS(n,st); 82 } 83 int ans=MAX*10+((1+MAX)*MAX)/2;//求出要求的答案 84 printf("%d\n",ans); 85 return 0; 86 }
原文：https://www.cnblogs.com/jiamian/p/11873020.html