郭博鈞

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int root,res, finalmaxchilddis;
   
4. int n;
   
5. struct Node
   
6. {
   
7.    int h=0,maxchilddis=-1,parent=-1,max=-1,sec=-1;
   
8.    vector<int> child;
   
9. };
   
10. int main()
    
11. {
    
12.     while(cin>>n)
    
13.     {
    
14.         finalmaxchilddis=-1;
    
15.         Node node[n];
    
16.         for(int i=0;i<n-1;i++)
    
17.         {
    
18.             int p,c;
    
19.             cin>>p>>c;
    
20.             node[c].parent=p;
    
21.             node[p].child.push_back(c);
    
22.         }
    
23.         for(int i=0;i<n;i++)
    
24.         {
    
25.             if(node[i].parent==-1)
    
26.             {
    
27.                 root=i;
    
28.             }
    
29.             if(node[i].child.size()==0)
    
30.             {
    
31.                 int h=0;
    
32.                 int parent=node[i].parent;
    
33.                 while(parent!=-1)
    
34.                 {
    
35.                   h++;
    
36.                   if(h>node[parent].h)
    
37.                     node[parent].h=h;
    
38.                   else
    
39.                     break;
    
40.                     parent=node[parent].parent;
    
41.                 }
    
42.             }
    
43.         }
    
44. 
    
45.         for(int i=0;i<n;i++)
    
46.         {
    
47.              if(node[i].child.size()>=2)
    
48.             {
    
49. 
    
50.                 for(int j=0;j<node[i].child.size();j++)
    
51.                 {
    
52.                   int childh=node[node[i].child[j]].h;
    
53.                   
    
54.                   
    
55.                   if(childh>node[i].max)
    
56.                   {
    
57.                       node[i].sec=node[i].max;
    
58.                       node[i].max=childh;
    
59.                   }
    
60.                   else if(childh>node[i].sec)
    
61.                       node[i].sec=childh;
    
62.                 }
    
63.                 node[i].maxchilddis=node[i].max+node[i].sec+2;
    
64.                 if(node[i].maxchilddis>finalmaxchilddis)
    
65.                 {
    
66.                     finalmaxchilddis=node[i].maxchilddis;
    
67.                 }
    
68.             }
    
69.         }
    
70. 
    
71.         if(node[root].h>finalmaxchilddis)
    
72.         {
    
73.              res=node[root].h;
    
74.         }else
    
75.         {
    
76.              res=finalmaxchilddis;
    
77.         }
    
78.                         
    
79.     cout<<res<<endl;
    
80. 
    
81.     }
    
82. 
    
83.     return 0;
    
84. }

複製代碼