BZOJ1149:[CTSC2007]风玲Mobiles

Description

Input

Output

输出仅包含一个整数。表示最少需要多少次交换能使风铃满足Ike的条件。如果不可能满足，输出-1。

Sample Input

6
2 3
-1 4
5 6
-1 -1
-1 -1
-1 -1

Sample Output

题解：

直接一次DFS即可。

若两棵子树中玩具深度差>1，输出-1。

若两颗子数内部玩具深度差都>0，输出-1。

若左子树中存在比右子树深度小的玩具，inc(ans)。

我竟然WA了一发，可悲。

代码：

 1 uses math;
 2 var
 3   i,j,k,l,n,m,cnt,ans:longint;
 4   a:array[0..200011,1..2]of longint;
 5   dep,mi,ma:array[0..200011]of longint;
 6 function ss(x,fa,y:longint):longint;
 7 begin
 8   if x=-1 then
 9   begin
10     inc(cnt); dep[cnt]:=dep[fa]+1; a[fa,y]:=cnt;
11     mi[cnt]:=dep[cnt]; ma[cnt]:=dep[cnt];
12     exit;
13   end;
14   dep[x]:=dep[fa]+1;
15   ss(a[x,1],x,1); ss(a[x,2],x,2);
16   if ma[a[x,1]]-mi[a[x,2]]>1 then begin writeln(-1); halt; end;
17   if ma[a[x,2]]-mi[a[x,1]]>1 then begin writeln(-1); halt; end;
18   if(ma[a[x,1]]-mi[a[x,1]]>0)and(ma[a[x,2]]-mi[a[x,2]]>0)then
19   begin writeln(-1); halt; end;
20   ma[x]:=max(ma[a[x,1]],ma[a[x,2]]); mi[x]:=min(mi[a[x,1]],mi[a[x,2]]);
21   if mi[a[x,1]]<ma[a[x,2]] then inc(ans);
22 end;
23 begin
24   readln(n); cnt:=n;
25   for i:=1 to n do readln(a[i,1],a[i,2]);
26   ss(1,0,0); writeln(ans);
27 end.

View Code