记录编号	21731	评测结果	WWWAWWAWWA
题目名称	489.树的最大匹配	最终得分	30
用户昵称	reamb	是否通过	未通过
代码语言	Pascal	运行时间	0.005 s
提交时间	2010-11-13 19:09:56	内存使用	2.04 MiB

{wo cao xia xing qi zhe ge shi hou jiu gai lian sai le
wo jing ran hai zai xie ti...ungelivable--anoier_hnfkgy}
program treeb;
var
  pp:array[1..1000,0..1]of longint;
  f:array[1..1000,0..1]of int64;
  g:array[1..1000,0..1000]of integer;
  l,n,x,p,i,j,gen,jilu:longint;
  biaozhi:array[1..1000]of boolean;
  d:int64;
function max(a,b:longint):longint;
begin
  if a>b then
  begin
    max:=a;
    jilu:=1
  end
  else
  begin
    max:=b;
    jilu:=0
  end
end;
procedure treedp(k:integer);
var
  i:integer;
begin
  if g[k,0]=0 then
  begin
    pp[k,0]:=0;
    pp[k,1]:=0;
    f[k,0]:=1;
    f[k,1]:=1;
    exit
  end;
  f[k,0]:=1;
  for i:=1 to g[k,0] do
  begin
    treedp(g[k,i]);
    pp[k,0]:=pp[k,0]+max(pp[g[k,i],1],pp[g[k,i],0]);
    f[k,0]:=f[k,0]*f[g[k,i],jilu]
  end;
  l:=0;
  for i:=1 to g[k,0] do
    if pp[k,0]-max(pp[g[k,i],1],pp[g[k,i],0])+pp[g[k,i],0]+1>l then
    begin
      l:=pp[k,0]-max(pp[g[k,i],1],pp[g[k,i],0])+pp[g[k,i],0]+1;
      f[k,1]:=f[k,0]div f[g[k,i],jilu]*f[g[k,i],0]
    end
    else
      if pp[k,0]-max(pp[g[k,i],1],pp[g[k,i],0])+pp[g[k,i],0]+1=l then
       begin
         f[k,1]:=f[k,1]+f[k,0]div f[g[k,i],jilu]*f[g[k,i],0]
       end;
  pp[k,1]:=l
end;
begin
  assign (input,'treeb.in');
  reset (input);
  assign (output,'treeb.out');
  rewrite (output);
    readln (n);
    fillchar(biaozhi,sizeof(biaozhi),true);
    for i:=1 to n do
    begin
      read (x,g[x,0]);
      for j:=1 to g[x,0] do
      begin
        read (g[x,j]);
        biaozhi[g[x,j]]:=false
      end;
      readln
    end;
    for i:=1 to n do
      if biaozhi[i] then
      begin
        gen:=i;
        break
      end;
    treedp(gen);
    p:=max(pp[gen,1],pp[gen,0]);
    writeln (p);
    if pp[gen,1]=pp[gen,0] then
    begin
      d:=f[gen,0]+f[gen,1];
      writeln (d)
    end
    else
      writeln (f[gen,jilu]);
  close (input);
  close (output)
end.