江家同

1. APCS 實作題：

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

複製代碼

2. APCS 觀念題：
10510 - 12
(B)
10510 - 13
(B)