1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include<bits/stdc++.h>
#define N 100010
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define fsb(a,b,c) for(int (a)=(b);(a)<=(c);(a)++)
#define fbs(a,b,c) for(int (a)=(b);(a)>=(c);(a)--)
using namespace std;
struct node{
int ls,rs,l1,l2,r1,r2;
}a[N];
int n,mx=0,mn=99999999,ans=0,flag=1;
template<typename qw>inline void rll(qw &x){
x=0;qw f=1;char c=getchar();
while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
x*=f;
}
inline void dfs(int u,int d){
if(u==-1)return;
if(a[u].ls==-1||a[u].rs==-1)mx=max(mx,d),mn=min(mn,d);
dfs(a[u].ls,d+1);dfs(a[u].rs,d+1);
}
inline void dfs2(int u,int d){
int ls=a[u].ls,rs=a[u].rs,&l1=a[u].l1,&l2=a[u].l2,&r1=a[u].r1,&r2=a[u].r2;
if(ls==-1){
if(d==mn)l1=1;else l2=1;
}else{
dfs2(ls,d+1);
if(flag==0)return;
l1=a[ls].l1|a[ls].r1;
l2=a[ls].l2|a[ls].r2;
}
if(rs==-1){
if(d==mn)r1=1;else r2=1;
}else{
dfs2(rs,d+1);
if(flag==0)return;
r1=a[rs].l1|a[rs].r1;
r2=a[rs].l2|a[rs].r2;
}
if(l1+l2+r1+r2==4){
flag=0;return;
}
if(l1==1&&r2==1)ans++;
}
int main(){
rll(n);
fsb(i,1,n){
rll(a[i].ls);rll(a[i].rs);
}
dfs(1,1);
if(mx-mn>1)flag=0;else dfs2(1,1);
printf("%d\n",(flag==0)?-1:ans);
return 0;
}
|