[HOJ] 228 Mobiles

兩邊子樹最大深度都>0無解
任意節點深度差>1無解

#include<cstdio>
#include<algorithm>
#define INF 1000000000
using namespace std;
struct node{
    int l,r,mn,mx;
}t[100005];
int n,l,r,cnt,f;
void dfs(int k){
    if(!k)return;
    t[k].mx=1;
    t[k].mn=INF;
    if(t[k].l){
        dfs(t[k].l);
        t[k].mn=min(t[k].mn,t[t[k].l].mn+1);
        t[k].mx=max(t[k].mx,t[t[k].l].mx+1);
    }
    if(t[k].r){
        dfs(t[k].r);
        t[k].mn=min(t[k].mn,t[t[k].r].mn+1);
        t[k].mx=max(t[k].mx,t[t[k].r].mx+1);
    }
    if(!t[k].l||!t[k].r)t[k].mn=1;
}
void dfs1(int k){
    if(!k)return;
    if(t[t[k].l].mx-t[t[k].l].mn>0&&
    t[t[k].r].mx-t[t[k].r].mn>0){
        f=1;
        return;
    }
    if(t[k].mx==t[k].mn)return;
     
    if(t[k].mx-t[k].mn>1){
        f=1;
        return;
    }
    int R,L;
    R=t[t[k].r].mn+t[t[k].r].mx;
    L=t[t[k].l].mn+t[t[k].l].mx;
    if(L<R)cnt++;
    dfs1(t[k].l);
    dfs1(t[k].r);
}
int main(){
    scanf("%d",&n);
    int L,R;
    t[0].mn=t[0].mx=0;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&L,&R);
        if(L==-1)L=0;
        if(R==-1)R=0;
        t[i].l=L;
        t[i].r=R;
    }
         
    dfs(1);
    dfs1(1);
    if(!f)printf("%d\n",cnt);
    else puts("-1");
}