APCS 105年3月題4-血緣關係(C++參考)

APCS Y16M3-Q3 - 血緣關係
/*
apcs-4 : 105年3月5日 APCS 試題 Q4 - 血緣關係  , 原題應不需多測資，本參考解為多測資 EOF
  找每一葉節點的(最長距len、最大子樹高h1、次大子樹高h2)，求max(len, h1+h2)
*/

#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
const int MaxN = 100000; // n <= 100000
int pa[MaxN]; //父
vector <int> ch[MaxN]; //兒子們
int longlen(int x, int &h1, int &h2)
{
h1 = h2 = 0;  //子樹中最長高h1 及次長高h2
int len=0;
if(ch[x].size()==0) return 0;  //葉節點的高為 0
for(int i=0; i<ch[x].size(); ++i)
{
int sh1, sh2;
int y = ch[x][i];
int slen = longlen(y, sh1, sh2);  //遞迴找出各子樹的最長距 slen(i) -> len
len = max(len,slen);
if( sh1>=h2 ) // 子樹中的最長子樹若比 本子樹的次長子樹大，重排 h1,h2
{
h2=sh1+1;
  if(h2>h1) // swap(h1,h2)
{
sh1 = h1;
h1 = h2;
h2 = sh1;
  }
}
}
return max(len,h1+h2);
}

int main(void)
{
int j,h , n , a,b;
while( cin >> n )
{
memset(pa,-1,sizeof(pa));
for(j=0; j<n; ++j) ch[j].clear();
// 讀 n-1 筆 關係
for(j=1;j<n;++j) // n-1 筆
{
cin >> a >> b;
ch[a].push_back(b);
     pa[b]=a;  // 上次少這行 2017/2/4更新
}
int rt;
for(rt=0; rt<n; ++rt) if(pa[rt] == -1 ) break;  //找根
int h1,h2;
cout << longlen(rt,h1,h2) << endl;
}
return 0;
}
/*範例輸入：
8
0 1
0 2
0 3
7 0
1 4
1 5
3 6

4
0 1
0 2
2 3

10
1 5
1 4
7 0
3 6
0 3
0 2
0 1
0 9
7 8

14
3 5
1 3
1 4
10 12
11 13
8 10
9 11
4 6
4 7
0 2
0 1
7 9
6 8

---------範例輸出：
4
3
4
8
*/