bzoj 1149 [CTSC2007]风玲Mobiles dfs

bzoj 1149 [CTSC2007]风玲Mobiles dfs"/>

bzoj 1149 [CTSC2007]风玲Mobiles dfs

题意：给定一棵完全二叉树，可以交换某个节点的左右儿子，求最少交换多少次可以使所有的叶节点深度相差不超过1,且深度较大的叶节点都在深度较小的叶节点左侧（来自po姐）。

题解：其实这题你看懂题目你就赢了。。。直接做。。这应该是CTSC中最水的一道了巴。dfs两遍，随便跑。然而并没有1A，因为空间开小了。。。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<iostream>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=1e6;
int l[N],r[N],ans,minx=1e9,maxx,n;
inline void dfs(int x,int dep)
{if (x==-1){maxx=max(maxx,dep);minx=min(minx,dep);return;}dfs(l[x],dep+1);dfs(r[x],dep+1);}
inline int solve(int x,int dep)
{int a,b;if (x==-1){if (dep==minx)return 1;return 2;}a=solve(l[x],dep+1);b=solve(r[x],dep+1);if (a==1&&b==2||a==1&&b==3||a==3&&b==2) ans+=1;  if (a==3&&b==3){printf("-1\n");exit(0);}  return a|b;  
}
int main()
{scanf("%d",&n);fo(i,1,n)scanf("%d%d",&l[i],&r[i]);dfs(1,0);if (maxx-minx>=2){printf("-1\n");return 0;}if (maxx==minx){printf("0\n");return 0;}solve(1,0);printf("%d\n",ans);return 0;
}