ac1068.pas

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

program tju1068;
const
  maxn=30000;
  maxq=32767;
var
  en,ep:array[3..maxn*2]of word;
  el,lv,root:array[1..maxn]of word;
  qn,qp:array[1..maxq*2]of word;
  ql:array[1..maxq]of word;
  n,i,x,y,ans:cardinal;
procedure pathcomp(x:word);
  var
    r,t:word;
  begin
    r:=x;while r<>root[r] do r:=root[r];
    while root[x]<>r do begin t:=root[x];root[x]:=r;x:=t;end;
  end;
procedure lca(father,x:word);
  begin
    lv[x]:=lv[father]+1;root[x]:=x;
    while ql[x]<>0 do begin
      if lv[qn[ql[x]]]>0 then begin
        pathcomp(qn[ql[x]]);
        inc(ans,lv[x]+lv[qn[ql[x]]]-lv[root[qn[ql[x]]]]*2);
      end;
      ql[x]:=qp[ql[x]];
    end;
    while el[x]<>0 do begin
      if lv[en[el[x]]]=0 then lca(x,en[el[x]]);
      el[x]:=ep[el[x]];
    end;
    root[x]:=root[father];
  end;
begin
  repeat
    read(n);
    for i:=2 to n do begin
      read(x,y);
      en[i*2-1]:=y;ep[i*2-1]:=el[x];el[x]:=i*2-1;
      en[i*2]:=x;ep[i*2]:=el[y];el[y]:=i*2;
    end;

    read(n);y:=1;
    for i:=1 to n do begin
      x:=y;read(y);if x=y then continue;
      qn[i*2-1]:=y;qp[i*2-1]:=ql[x];ql[x]:=i*2-1;
      qn[i*2]:=x;qp[i*2]:=ql[y];ql[y]:=i*2;
    end;

    fillchar(lv,sizeof(lv),0);
    fillchar(root,sizeof(root),0);
    ans:=0;
    lca(1,1);
    writeln(ans);
  until seekeof;
end.