本来挺水的题，却花了我好久时间啊，后来发现是一个边界出错了。唉。
然后，这道题就是直接做就行了。
需要注意的是如果递归深度超过32，可以直接判断无解，避免数据中出现变态的链。
CO
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-4-19
DESCRIPTION:
$DESCRIPTION
*/
#include <stdio.h>
#define MAXN 100000
#define NOCHILD -1
#define MAXDEPTH 32
#define MAX(a,b) ((a)>(b)?(a):(b))
#define get_height(root) ((root)==NOCHILD?0:height[(root)])
#define get_have(root) ((root)==NOCHILD?0:have[(root)])
#define is_full(height,have) (((1<<height)-1)==have)
struct Tree{int left,right;};
int n;
Tree tree[MAXN];
int height[MAXN];
long long int have[MAXN];
bool noanswer;
int answer;
int dfs_get_height(int root,int depth=1)
{
if (depth>MAXDEPTH)
return noanswer=true;
if (root==NOCHILD) return 0;
else
{
int left_height=dfs_get_height(tree[root].left,depth+1);
int right_height=dfs_get_height(tree[root].right,depth+1);
return height[root]=MAX(left_height,right_height)+1;
}
}
long long int dfs_get_have(int root,int depth=1)
{
if (depth>MAXDEPTH)
return noanswer=true;
if (root==NOCHILD) return 0;
else
{
long long int left_have=dfs_get_have(tree[root].left,depth+1);
long long int right_have=dfs_get_have(tree[root].right,depth+1);
return have[root]=left_have+right_have+1;
}
}
bool dfs_judge(int root)
{
if (noanswer) return false;
if (root==NOCHILD) return true;
int left=tree[root].left;
int right=tree[root].right;
int left_height=get_height(left);
int right_height=get_height(right);
long long int left_have=get_have(left);
long long int right_have=get_have(right);
bool left_is_full=is_full(left_height,left_have);
bool right_is_full=is_full(right_height,right_have);
if (left_height==right_height)
{
if (left_is_full)
return dfs_judge(right);
else if (right_is_full)
{
answer++;
return dfs_judge(left);
}
else return false;
}
else if (left_height+1==right_height)
{
if (right_is_full)
{
answer++;
return dfs_judge(left);
}
else if (left_is_full)
{
answer++;
return dfs_judge(right);
}
else return false;
}
else if (left_height==right_height+1)
{
if (left_is_full)
return dfs_judge(right);
else if (right_is_full)
return dfs_judge(left);
else return false;
}
else return false;
}
int main()
{
//freopen(“mobiles.in”,”r”,stdin);
//freopen(“mobiles.out”,”w”,stdout);
scanf(“%d\n”,&n);
for (int i=0;i<n;i++)
{
int l,r;
scanf(“%d %d\n”,&l,&r);
if (l>0) tree[i].left=l-1;
else tree[i].left=NOCHILD;
if (r>0) tree[i].right=r-1;
else tree[i].right=NOCHILD;
}
dfs_get_height(0);
dfs_get_have(0);
if (dfs_judge(0)) printf(“%d\n”,answer);
else printf(“-1\n”);
//fclose(stdin);
//fclose(stdout);
return 0;
}