https://www.lydsy.com/JudgeOnline/problem.php?id=1149
https://www.luogu.org/problemnew/show/P3621
sb贪心，然而跪了两次才A……一次还是我自己出的样例都没过结果就交了……
dep[i]表示i子树最深深度，up[i]表示i子树是否有不同层的风铃。
那么深搜一下就行了，判断方法看我代码吧……懒得讲了。
#include<cmath> #include<queue> #include<vector> #include<cstdio> #include<cctype> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=1e5+5; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } int n,ch[N][2],dep[N],up[N]; bool ok; void dfs1(int u){ int l=ch[u][0],r=ch[u][1]; if(!l)dep[u]=1; else{ dfs1(l);dep[u]=dep[l]+1; } int tmp; if(!r)tmp=1; else{ dfs1(r);tmp=dep[r]+1; } if(abs(tmp-dep[u])>1)ok=1; else if(abs(tmp-dep[u])==1)up[u]=1; dep[u]=max(dep[u],tmp); up[u]|=up[ch[u][0]];up[u]|=up[ch[u][1]]; } int ans; void dfs2(int u){ if(!u)return; if(dep[ch[u][0]]<dep[ch[u][1]]){ swap(ch[u][0],ch[u][1]);ans++; } else if(dep[ch[u][0]]==dep[ch[u][1]]){ if(up[ch[u][0]]&&up[ch[u][1]])ok=1; else if(up[ch[u][0]]){ swap(ch[u][0],ch[u][1]);ans++; } } dfs2(ch[u][0]);dfs2(ch[u][1]); } int main(){ n=read(); for(int i=1;i<=n;i++){ ch[i][0]=read(),ch[i][1]=read(); if(ch[i][0]==-1)ch[i][0]=0; if(ch[i][1]==-1)ch[i][1]=0; } dep[0]=0; dfs1(1); dfs2(1); printf("%d ",ok?-1:ans); return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++