树上最远距离

给定一颗N个节点的树，结点从1到N编号。

现在要计算对于每个结点i，到它最远的结点是多少距离，这个值记为 $S_iSi。$

输入

第一行输入两个整数 $10^4)N(2≤N≤104)。$

接下来N-1行，每行两个整数 $x_i, y_i (1 le x_i, y_i le n, x_i e 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
",max(deep[2][i],deep[3][i]));
60     }
61     return 0;
62 }

输出

提示

结点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 。$