NTPFECT - Đại diện hoàn hảo
Tác giả: RR
Ngôn ngữ: Pascal
{$MODE OBJFPC}
uses math;
const
FINP = '';
FOUT = '';
MAXN = 1011;
type
list = ^node;
node = record
u : longint;
next : list;
end;
var
f1,f2 : text;
n : longint;
ke : array[1..MAXN] of list;
f,g,h : array[1..MAXN] of longint;
visited : array[1..MAXN] of boolean;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure add(u:longint; var a:list);
var
p:list;
begin
new(p); p^.u:=u;
p^.next:=a; a:=p;
end;
procedure del(var a:list);
begin
if a=nil then exit;
del(a^.next);
dispose(a);
end;
procedure inp;
var
i,u,v:longint;
begin
fillchar(ke,sizeof(ke),0);
fillchar(f,sizeof(f),0);
fillchar(g,sizeof(g),0);
fillchar(h,sizeof(h),0);
fillchar(visited,sizeof(visited),false);
for i:=2 to n do
begin
read(f1,u,v);
add(u,ke[v]);
add(v,ke[u]);
end;
end;
procedure dfs(u:longint);
var
p:list;
v,x,now:longint;
begin
visited[u]:=true;
p:=ke[u]; x:=0; now:=high(longint);
f[u]:=1;
while p<>nil do
begin
v:=p^.u; p:=p^.next;
if visited[v] then continue;
dfs(v);
if f[v]-min(f[v],g[v])<now then
begin
x:=v;
now:=f[v]-min(f[v],g[v]);
end;
inc(f[u],min(min(f[v],g[v]),h[v]));
inc(g[u],min(f[v],g[v]));
inc(h[u],g[v]);
end;
if x=0 then g[u]:=MAXN
else g[u]:=g[u]+f[x]-min(f[x],g[x]);
end;
procedure solve;
begin
dfs(1);
writeln(f2,min(f[1],g[1]));
end;
begin
openF;
read(f1,n);
while (n>0) do
begin
inp;
if n<=3 then writeln(f2,1)
else solve;
for n:=1 to n do
del(ke[n]);
read(f1,n);
end;
closeF;
end.