给定一颗N个节点的树，结点从1到N编号。
现在要计算对于每个结点i，到它最远的结点是多少距离，这个值记为S_iSi?。
第一行输入两个整数N(2 \le N \le 10^4)N(2≤N≤104)。
接下来N-1行，每行两个整数x_i, y_i (1 \le x_i, y_i \le n, x_i \ne y_i)xi?,yi?(1≤xi?,yi?≤n,xi??=yi?), 表示x_i, y_ixi?,yi?之间有一条边。
输入保证是一棵树。
第i行输出S_iSi?。
1 /************************************************************************* 2 > Author: Henry Chen 3 > Mail: 390989083@qq.com 4 > Created Time: 鍥? 8/27 18:58:00 2020 5 ************************************************************************/ 6 7 #include<bits/stdc++.h> 8 using namespace std; 9 vector<pair<int,int> >vec[10001]; 10 int deep[5][10001]; 11 void dfs(int u,int fa,int dep,int p) 12 { 13 // << u << endl; 14 deep[p][u] = dep; 15 for(int i = 0;i < vec[u].size();i++) 16 { 17 int v = vec[u][i].first; 18 if(v != fa) 19 { 20 dfs(v,u,dep+vec[u][i].second,p); 21 } 22 } 23 } 24 int main() 25 { 26 int n; 27 cin >> n; 28 for(int i = 2;i <= n;i++) 29 { 30 int u,v; 31 scanf("%d%d",&u,&v); 32 vec[i].push_back(make_pair(u,v)); 33 vec[u].push_back(make_pair(i,v)); 34 } 35 dfs(1,1,0,1); 36 int mx = 0; 37 int num; 38 for(int i = 1;i <= n;i++) 39 { 40 if(mx < deep[1][i]) 41 { 42 num = i; 43 mx = deep[1][i]; 44 } 45 } 46 dfs(num,num,0,2); 47 mx = 0; 48 for(int i = 1;i <= n;i++) 49 { 50 if(mx < deep[2][i]) 51 { 52 num = i; 53 mx = deep[2][i]; 54 } 55 } 56 dfs(num,num,0,3); 57 for(int i = 1;i <= n;i++) 58 { 59 printf("%d\n",max(deep[2][i],deep[3][i])); 60 } 61 return 0; 62 }
5 1 1 2 1 3 1 1 1
3 2 3 4 4
结点4到结点1最远， S_1 = 3 S1?=3 。
结点4和结点5到结点2都是最远的， S_2 = 2 S2?=2 。
结点5到结点3距离最远， S_3 = 3 S3?=3 。
结点5到结点4距离最远， S_4 = 4 S4?=4 。
结点4到结点5距离最远， S_5 = 4 S5?=4 。
原文：https://www.cnblogs.com/mzyy1001/p/13574463.html