比赛 20110923 评测结果 AAAAAAAAAA
题目名称 拜访奶牛 最终得分 100
用户昵称 wo shi 刘畅 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2011-09-23 21:25:20
显示代码纯文本
var
  x,y,i,n,total:longint;
  point,next:array[0..200000]of longint;
  f:array[0..200000,0..10]of longint;
  v:array[0..200000]of boolean;

procedure bian(x,y:longint);
begin
  inc(total);
  point[total]:=y;
  next[total]:=next[x];
  next[x]:=total;

  inc(total);
  point[total]:=x;
  next[total]:=next[y];
  next[y]:=total;
end;

function max(x,y:longint):longint;
begin
  if x>y then exit(x);
  exit(y);
end;

function go(k,m:longint):longint;
var
  i,value,now:longint;
  yes:boolean;

begin
  if f[k,m]>0 then exit(f[k,m]);
  i:=next[k];
  value:=0;
  yes:=false;
  v[k]:=true;
  while i>0 do
  begin
    now:=point[i];
    if not v[now] then
    begin
      yes:=true;
      if m=1 then value:=value+go(now,0)
      else value:=value+max(go(now,1),go(now,0));
    end;
    i:=next[i];
  end;
  if not yes then
  begin
    if m=1 then
    begin
      f[k,m]:=1;
      v[k]:=false;
      exit(1);
    end
    else begin
      f[k,m]:=0;
      v[k]:=false;
      exit(0);
    end;
  end;
  v[k]:=false;
  if m=1 then inc(value);
  f[k,m]:=value;
  go:=value;
end;

begin
  assign(input,'vacation.in'); reset(input);
  assign(output,'vacation.out'); rewrite(output);
  readln(n);
  total:=n;
  for i:=1 to n-1 do
  begin
    read(x,y);
    bian(x,y);
  end;
  writeln(max(go(1,0),go(1,1)));
  close(input);
  close(output);
end.