Poj 3246 Balanced Lineup（線段樹基礎）

題目描述 Description     給出一個二叉樹，輸出它的最大寬度和高度。   輸入描述 Input Description 第一行一個整數n。   下面n行每行有兩個數，是這個二叉樹連接到的節點的編號，如果沒有連接到節點，則為0。   輸出描述 Output Description 輸出共一行，輸出二叉樹的最大寬度和高度，用一個空格隔開。   樣例輸入 Sample Input 5   2 3   4 5   0 0   0 0   0 0   樣例輸出 Sample Output 2 3  

#include<iostream>   
#include<cstdio>   
#include<cstring>   
#include<cmath>   
#include<algorithm>   
#include<bitset>   
#include<iomanip>   
  
using namespace std;  
  
int a[ 40 ][ 3 ] = { 0 } , num[ 40 ] ;  
  
int w = 0 , d = 0 ;  
void dfs( int x , int y )  
{  
    num[ y ]++ ;  
    if( y > w )  
        w = y ;  
    if( a[ x ][ 1 ] != 0 )  
        dfs( a[ x ][ 1 ] , y + 1 ) ;  
    if( a[ x ][ 2 ] != 0 )  
        dfs( a[ x ][ 2 ] , y + 1 ) ;  
}  
int main()  
{  
    int n ;  
    cin >> n ;  
    for( int i = 1 ; i <= n ; i++)  
        cin >> a[ i ][ 1 ] >> a[ i ][ 2 ] ;  
    dfs( 1 , 1 ) ;  
    for( int i = 1 ; i <= 16 ; ++i )  
        if( num[ i ] > d )  
            d = num[ i ] ;  
    cout << d << " " << w << endl ;  
    return 0 ;  
}  

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<iomanip>

using namespace std;

int a[ 40 ][ 3 ] = { 0 } , num[ 40 ] ;

int w = 0 , d = 0 ;
void dfs( int x , int y )
{
num[ y ]++ ;
if( y > w )
w = y ;
if( a[ x ][ 1 ] != 0 )
dfs( a[ x ][ 1 ] , y + 1 ) ;
if( a[ x ][ 2 ] != 0 )
dfs( a[ x ][ 2 ] , y + 1 ) ;
}
int main()
{
int n ;
cin >> n ;
for( int i = 1 ; i <= n ; i++)
cin >> a[ i ][ 1 ] >> a[ i ][ 2 ] ;
dfs( 1 , 1 ) ;
for( int i = 1 ; i <= 16 ; ++i )
if( num[ i ] > d )
d = num[ i ] ;
cout << d << " " << w << endl ;
return 0 ;
}