记录编号	138910	评测结果	AAAAAAAAAA
题目名称	[USACO Nov10] 拜访奶牛	最终得分	100
用户昵称	传奇	是否通过	通过
代码语言	Pascal	运行时间	0.062 s
提交时间	2014-11-07 08:54:23	内存使用	1.07 MiB

program cojs593;
type
  apoint=^node;
  node=record
    xb:longint;
    next:apoint;
  end;
var
  a,b:array[0..50000] of apoint;
  f:array[0..50000,0..1] of longint;
  vi:Array[0..50000] of boolean;
  v1:array[0..50000,0..1] of boolean;
  i,j,k,m,n,c1,c2:longint;
procedure add(l,r:longint);
var
  p:apoint;
begin
  new(p);
  p^.xb:=r;
  p^.next:=a[l];
  a[l]:=p;
end;
procedure add2(l,r:longint);
var
  p:apoint;
begin
  new(p);
  p^.xb:=r;
  p^.next:=b[l];
  b[l]:=p;
end;
procedure dfs(x:longint);
var
  p:apoint;
begin
  vi[x]:=false;
  p:=a[x];
  while p<>nil do
    begin
      if vi[p^.xb] then
        begin
          add2(x,p^.xb);
          dfs(p^.xb);
        end;
      p:=p^.next;
    end;
end;
function max(a,b:longint):longint;
begin
  if a>b then exit(a);
  exit(b);
end;

procedure treedp(x,z:longint);
var
  i,j,k,l:longint;
  p:apoint;
begin
  if v1[x,z] then exit;
  p:=b[x];
  if p=nil then
    begin
      if z=1 then f[x,z]:=1;
      v1[x,z]:=true;
      exit;
    end;
  k:=0;
  if z=0 then
      while p<>nil do
        begin
          treedp(p^.xb,1);
          treedp(p^.xb,0);
          inc(k,max(f[p^.xb,1],f[p^.xb,0]));
          p:=p^.next;
        end;
  p:=b[x];
  l:=0;
  while p<>nil do
    begin
      treedp(p^.xb,0);
      inc(l,f[p^.xb,0]);
      p:=p^.next;
    end;
  f[x,z]:=max(l,k);
  if z=1 then inc(f[x,z]);

  v1[x,z]:=true;
end;
begin
  assign(input,'vacation.in');
  assign(output,'vacation.out');
  reset(input);
  rewrite(output);

  readln(n);
  for i:=1 to n-1 do
    begin
      readln(c1,c2);
      add(c1,c2);
      add(c2,c1);
    end;
  fillchar(vi,sizeof(vi),true);
  dfs(1);
  fillchar(f,sizeof(f),0);
  fillchar(v1,sizeof(v1),false);
  treedp(1,1);
  treedp(1,0);
  writeln(max(f[1,1],f[1,0]));

  close(input);
  close(output);
end.