本文主要是介绍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 ;
}
这篇关于ZOJ 3805 Machine的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
