分析：
由于最大最小相差深度小于等于1，所以可以先dfs一遍，特判一下，0输出0，大于1就是-1（考试时候忘了特判就挂了），对于等于1情况，我们来分析一下什么时候需要翻转：
- 左小右大
- 左有小有大，右大
- 左小，右有小有大
所以，对于这个需要再来一次dfs，用0表示小，1表示大，2表示有小有大，遇到上面三种情况就ans++
完整代码如下：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define re register
#define gc getchar()
#define ll long long
#define il inline
const int N= ;
il int read() {
re int x(),f();
re char ch=gc;
while(ch<''||ch>'') {
if(ch=='-') f=-;
ch=gc;
}
while(ch>=''&&ch<='') {
x=(x<<)+(x<<)+(ch^);
ch=gc;
}
return x*f;
}
int ls[N],rs[N],_max=-,_min=1e8,deep[N],n,ans,flag=; void dfs1(int u) {
if(ls[u]) {
deep[ls[u]]=deep[u]+;
dfs1(ls[u]);
} else {
_min=min(_min,deep[u]+);
_max=max(_max,deep[u]+);
}
if(rs[u]) {
deep[rs[u]]=deep[u]+;
dfs1(rs[u]);
} else {
_min=min(_min,deep[u]+);
_max=max(_max,deep[u]+);
}
} namespace SP1 {
int x[][]= {
,,,
,,,
,,,
};
int dfs(int u,int dep) {
if(u==-) {
if(dep==_max-) return ;
return ;
}
int a=dfs(ls[u],dep+);
int b=dfs(rs[u],dep+);
if(a==&&b==) ++ans;
if(a==&&b==) ++ans;
if(a==&&b==) ++ans;
if(a==&&b==) flag=;
return x[a][b];
}
int main() {
dfs(,);
if(!flag) {
cout<<-<<endl;
return ;
}
cout<<ans<<endl;
}
};
int main() { n=read();
for(int i=; i<=n; ++i)
ls[i]=read(),rs[i]=read();
dfs1();
if(_max-_min==) {
SP1::main();
return ;
}
if(_max==_min) cout<<;
cout<<-; return ;
}
很多大佬莫名MLE了，但是这个的空间是足够的，只用了16M