ZOJ 3805 Machine

题目链接~~>

做题感悟：比赛时想到方法了，但是没能AC，很遗憾，没有考虑到左右子树的右节点相等的情况，结果就杯具了，比赛完后捋了一下思路就AC了，说明比赛时很不淡定，头脑不清醒，以后要注意。

解题思路：

                题目给的就是一颗树，只是要把右节点多的放到左儿子上就好，这样减少个数，递归一下，注意左右儿子节点相等的情况需要加 1 。

代码：

#include<iostream>
#include<sstream>
#include<map>
#include<cmath>
#include<fstream>
#include<queue>
#include<vector>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<bitset>
#include<ctime>
#include<string>
#include<cctype>
#include<iomanip>
#include<algorithm>
using namespace std  ;
#define INT __int64
#define L(x)  (x * 2)
#define R(x)  (x * 2 + 1)
const int INF = 0x3f3f3f3f ;
const double esp = 0.0000000001 ;
const double PI = acos(-1.0) ;
const int mod = 1000000007 ;
const int MY = (1<<5) + 5 ;
const int MX = 100000 + 5 ;
int n ;
struct node
{
    int le ,rt ;
}T[MX] ;
int dfs(int u)  // 转变左右子树，计算有几个右儿子
{
    int Lson = 0 ,Rson = 0 ,num = 0 ;
    if(T[u].le)        // 计算左子树
          Lson = dfs(T[u].le) ;
    if(T[u].rt)       //  计算右子树
          Rson = dfs(T[u].rt) ;
    if(Lson < Rson)   // 如果左子树的右儿子小于右子树的右儿子
        swap(T[u].le ,T[u].rt) ;
    if(Lson == Rson)  return Lson + 1 ;  // 注意
    return  max(Lson ,Rson) ;
}
int main()
{
    //freopen("input.txt" ,"r" ,stdin) ;
    int x ;
    while(~scanf("%d" ,&n))
    {
        memset(T ,0 ,sizeof(T)) ;
        for(int i = 2 ;i <= n ; ++i)
        {
            scanf("%d" ,&x) ;
            if(T[x].le)
                     T[x].rt = i ;
            else     T[x].le = i ;
        }
        printf("%d\n" ,dfs(1)) ;
    }
    return 0 ;
}