1 program Xiong;
2 uses
3 math;
4 type
5 rec=record
6 a,b:longint;
7 end;
8 var
9 n,m,i,t,s,a,b,j,q,k:longint;
10 oula,dep,app,list,next:array[0..100]of longint;
11 side:array[0..100]of rec;
12 f:array[0..100,0..100]of longint;
13
14 procedure make(a,b:longint);
15 var
16 k:longint;
17 begin
18 inc(s);
19 side[s].a:=a;
20 side[s].b:=b;
21 if list[a]=0 then
22 list[a]:=s
23 else begin
24 k:=list[a];
25 next[s]:=k;
26 list[a]:=s;
27 end;
28 end;
29
30 procedure all(i,d:longint);
31 var
32 k:longint;
33 begin
34 inc(t);
35 oula[t]:=i;
36 app[i]:=t;
37 dep[i]:=d;
38 k:=list[i];
39 while k<>0 do begin
40 all(side[k].b,d+1);
41 inc(t);
42 oula[t]:=i;
43 k:=next[k];
44 end;
45 end;
46
47 function min(a,b:longint):longint;
48 begin
49 if dep[a]<dep[b] then exit(a) else exit(b);
50 end;
51
52 begin
53 assign(input,'input.txt');reset(input);
54 assign(output,'output.txt');rewrite(output);
55
56 read(n,m);
57 for i:=1 to m do begin
58 read(a,b);
59 make(a,b);
60 end;
61
62 all(1,1);
63
64 for i:=1 to t do
65 f[i,0]:=oula[i];
66 for j:=1 to trunc(ln(t)/ln(2)) do
67 for i:=1 to t do
68 f[i,j]:=min(f[i,j-1],f[i+2**(j-1),j-1]);
69
70 read(q);
71 for i:=1 to q do begin
72 read(a,b);
73 if app[a]>app[b] then begin
74 k:=a;
75 a:=b;
76 b:=k;
77 end;
78 k:=trunc(ln(app[b]-app[a]+1)/ln(2));
79 writeln(min(f[app[a],k],f[app[b]-2**k+1,k]));
80 end;
81
82 close(input);
83 close(output);
84 end.
今天才写的ST算法……一直感觉自己缩进很漂亮的样子。
转载于:https://www.cnblogs.com/xiong298/archive/2012/04/25/2469652.html
