ac1168.pas

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

program tju1168;
const
  maxtrie=200000;
  maxwords=1000000;
  maxqueries=1500000;
var
  trie:array[0..maxtrie,'A'..'Z']of longint;
  pos:array[1..maxwords]of longint;
  query,pre:array[2..maxqueries*2+1]of longint;
  last,lv,root:array[0..maxtrie]of longint;
  ans:array[1..maxqueries]of longint;
  n,i,p,q,t:longint;
  c:char;
procedure pathcomp(x:longint);
  var
    r,t:longint;
  begin
    r:=x;while root[r]<>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:longint);
  var
    c:char;
  begin
    lv[x]:=lv[father]+1;root[x]:=x;
    while last[x]>0 do begin
      if lv[query[last[x]]]>0 then begin
        pathcomp(query[last[x]]);
        ans[last[x] shr 1]:=lv[root[query[last[x]]]];
      end;
      last[x]:=pre[last[x]];
    end;
    for c:='A' to 'Z' do
      if trie[x,c]>0 then
        lca(x,trie[x,c]);
    root[x]:=root[father];
  end;
begin
  readln(n);
  for i:=1 to n do begin
    p:=0;
    repeat
      read(c);
      if trie[p,c]=0 then begin inc(t);trie[p,c]:=t;end;
      p:=trie[p,c];
    until seekeoln;
    readln;pos[i]:=p;
  end;

  read(n);t:=1;
  for i:=1 to n do begin
    read(p,q);p:=pos[p];q:=pos[q];
    inc(t);query[t]:=q;pre[t]:=last[p];last[p]:=t;
    inc(t);query[t]:=p;pre[t]:=last[q];last[q]:=t;
  end;

  lv[0]:=-1;lca(0,0);

  for i:=1 to n do
    writeln(ans[i]);
end.