ac1147.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1147;
const
  maxn=1500;
var
  last:array[0..maxn-1]of word;
  pre,child:array[1..maxn*2]of word;
  v:array[0..maxn-1]of boolean;
  need:array[0..maxn-1,0..2]of word;
       {need[n,0]:how many soldiers are needed to keep all subtrees of n
                  safe but leave n itself unprotected
        need[n,1]:how many soldiers are needed to keep n and all its subtrees
                  safe but there's no soldier at n
        need[n,2]:how many soldiers are needed to keep n and all its subtrees
                  safe with a soldier at n}
  t,u,n,i,j,k,x,y,c:word;
function min(a,b:word):word;
  begin
    if a<b then min:=a else min:=b;
  end;
procedure cal(x:word);
  var
    leaf:boolean;
    y,m:word;
  begin
    v[x]:=true;leaf:=true;m:=maxint;
    while last[x]>0 do begin
      y:=child[last[x]];
      if not v[y] then begin
        leaf:=false;cal(y);

        if need[x,0]<maxint then
          if need[y,1]=maxint then need[x,0]:=maxint else inc(need[x,0],need[y,1]);

        inc(need[x,1],min(need[y,1],need[y,2]));
        if need[y,2]<need[y,1] then m:=0 else m:=min(m,need[y,2]-need[y,1]);

        inc(need[x,2],min(min(need[y,0],need[y,1]),need[y,2]));
      end;
      last[x]:=pre[last[x]];
    end;

    if leaf then begin
      need[x,0]:=0;need[x,1]:=maxint;need[x,2]:=1;
    end
    else begin
      inc(need[x,1],m);inc(need[x,2]);
    end;
  end;
begin
  read(t);
  for u:=1 to t do begin
    fillchar(last,sizeof(last),0);
    fillchar(v,sizeof(v),0);
    fillchar(need,sizeof(need),0);

    read(n);c:=0;
    for i:=1 to n do begin
      read(x,k);
      for j:=1 to k do begin
        read(y);
        inc(c);pre[c]:=last[x];child[c]:=y;last[x]:=c;
        inc(c);pre[c]:=last[y];child[c]:=x;last[y]:=c;
      end;
    end;

    cal(0);
    writeln(min(need[0,1],need[0,2]));
  end;
end.