【JSOI2015】字符串树

  1  map:array[0..2100000,‘a‘..‘z‘]of longint;
  2     t:array[0..2100000]of record
  3                            s:longint;
  4                           end;
  5     root:array[0..500000]of longint;
  6     head,vet,next,dep:array[1..500000]of longint;
  7     f:array[1..550000,0..18]of longint;
  8     len:array[1..500000]of string;
  9     n,i,x,y,tot,tmp,cnt,j,k,q:longint;
 10     zyd,ch1,ch:string;
 11 
 12 procedure add(a,b:longint;c:string);
 13 begin
 14  inc(tot);
 15  next[tot]:=head[a];
 16  vet[tot]:=b;
 17  len[tot]:=c;
 18  head[a]:=tot;
 19 end;
 20 
 21 procedure dfs1(u:longint);
 22 var e,v,i:longint;
 23 begin
 24  for i:=1 to 18 do
 25  begin
 26   if dep[u]<(1<<i) then break;
 27   f[u,i]:=f[f[u,i-1],i-1];
 28  end;
 29  e:=head[u];
 30  while e<>0 do
 31  begin
 32   v:=vet[e];
 33   if v<>f[u,0] then
 34   begin
 35    dep[v]:=dep[u]+1;
 36    f[v,0]:=u;
 37    dfs1(v);
 38   end;
 39   e:=next[e];
 40  end;
 41 end;
 42 
 43 procedure ins(var x:longint;i:longint);
 44 begin
 45  inc(cnt); t[cnt]:=t[x];
 46  map[cnt]:=map[x];
 47  x:=cnt; inc(t[x].s);
 48  if i<=length(zyd) then ins(map[x,zyd[i]],i+1);
 49 end;
 50 
 51 function query(a,b,c,i:longint):longint;
 52 begin
 53 // writeln(a,‘ ‘,b,‘ ‘,c);
 54  if i>length(zyd) then exit(t[a].s+t[b].s-t[c].s*2);
 55  exit(query(map[a,zyd[i]],map[b,zyd[i]],map[c,zyd[i]],i+1));
 56 end;
 57 
 58 procedure dfs2(u:longint);
 59 var e,v:longint;
 60 begin
 61  e:=head[u];
 62  while e<>0 do
 63  begin
 64   v:=vet[e];
 65   if v<>f[u,0] then
 66   begin
 67    root[v]:=root[u];
 68    zyd:=len[e];
 69    ins(root[v],1);
 70    dfs2(v);
 71   end;
 72   e:=next[e];
 73  end;
 74 end;
 75 
 76 procedure swap(var x,y:longint);
 77 var t:longint;
 78 begin
 79  t:=x; x:=y; y:=t;
 80 end;
 81 
 82 function lca(x,y:longint):longint;
 83 var i,d:longint;
 84 begin
 85  if dep[x]<dep[y] then swap(x,y);
 86  d:=dep[x]-dep[y];
 87  for i:=0 to 18 do
 88   if d and (1<<i)>0 then x:=f[x,i];
 89  for i:=18 downto 0 do
 90   if f[x,i]<>f[y,i] then
 91   begin
 92    x:=f[x,i]; y:=f[y,i];
 93   end;
 94  if x=y then exit(x);
 95  exit(f[x,0]);
 96 end;
 97 
 98 begin
 99  assign(input,‘strings.in‘); reset(input);
100  assign(output,‘strings.out‘); rewrite(output);
101  readln(n);
102  for i:=1 to n-1 do
103  begin
104   readln(ch);
105   j:=1; x:=0;
106   while (ch[j]>=‘0‘)and(ch[j]<=‘9‘) do
107   begin
108    x:=x*10+ord(ch[j])-ord(‘0‘);
109    inc(j);
110   end;
111   inc(j); y:=0;
112   while (ch[j]>=‘0‘)and(ch[j]<=‘9‘) do
113   begin
114    y:=y*10+ord(ch[j])-ord(‘0‘);
115    inc(j);
116   end;
117   inc(j);
118   ch1:=‘‘;
119   for k:=j to length(ch) do ch1:=ch1+ch[k];
120   add(x,y,ch1);
121   add(y,x,ch1);
122  end;
123 
124  //f[1,0]:=1;
125 
126  dfs1(1);
127  dfs2(1);
128  readln(q);
129  for i:=1 to q do
130  begin
131   readln(ch);
132   j:=1; x:=0;
133   while (ch[j]>=‘0‘)and(ch[j]<=‘9‘) do
134   begin
135    x:=x*10+ord(ch[j])-ord(‘0‘);
136    inc(j);
137   end;
138   inc(j); y:=0;
139   while (ch[j]>=‘0‘)and(ch[j]<=‘9‘) do
140   begin
141    y:=y*10+ord(ch[j])-ord(‘0‘);
142    inc(j);
143   end;
144   inc(j);
145   ch1:=‘‘;
146   for k:=j to length(ch) do ch1:=ch1+ch[k];
147   tmp:=lca(x,y);
148   zyd:=ch1;
149   writeln(query(root[x],root[y],root[tmp],1));
150  end;
151 
152  close(input);
153  close(output);
154 end.