郭博鈞

1. APCS 實作題：

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

複製代碼

2. APCS 觀念題：10510 - 12、13
B
A