# APIO2007[风铃/mobiles]

CODE:

/*

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];

int dfs_get_height(int root,int depth=1)

{

if (depth>MAXDEPTH)

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)

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 (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)

{

return dfs_judge(left);

}

else return false;

}

else if (left_height+1==right_height)

{

if (right_is_full)

{

return dfs_judge(left);

}

else if (left_is_full)

{

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);

else printf(“-1\n”);

//fclose(stdin);

//fclose(stdout);

return 0;

}