用rmq的思想做最近公共祖先的问题转化

以poj 1330为例，因为这道题只是询问一次，还不至于使用st算法，只是在这里说一下怎么做问题的转化，在一个树的深搜过程中，每个点都会被访问到两次，这样形成了一个欧拉序列，假设两个点a,b的最近公共祖先是c那么在深搜的时候，按照顺序访问，如果要从a转到b那么必定会经过一次c节点，从c节点转到b所在的子树上，也就是说，c节点是这个从a到b的所有经过的节点之中，深度最小的一个，我们只需要在第一次出现a和第一次出现c的序列之间去找深度最小的即为其最近公共祖先。即为区间最值问题，rmq问题

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 10005
 4 int firs[2*N-1];
 5 int lis[2*N-1];
 6 int deep[2*N-1];
 7 int ti,t,head[N];
 8 int deg[N];
 9 struct edge
10 {
11     int v;
12     int next;
13 };
14 edge e[N];
15 void init()
16 {
17     memset(head,-1,sizeof(head));
18     memset(firs,-1,sizeof(firs));
19     memset(deg,0,sizeof(deg));
20     ti=0;
21     t=0;
22 }
23 void add(int u,int v)
24 {
25     e[t].v=v;
26     e[t].next=head[u];
27     head[u]=t++;
28 }
29 void dfs(int u,int de)
30 {
31     lis[ti]=u;
32     deep[ti]=de;
33     firs[u]=ti;
34     ti++;
35     int i,v;
36     for(i=head[u];i>=0;i=e[i].next)
37     {
38         dfs(e[i].v,de+1);
39         lis[ti]=u;
40         deep[ti]=de;
41         ti++;
42     }
43 }
44 int main()
45 {
46     int n,i,j,a,b;
47     int tc;
48     scanf("%d",&tc);
49     int min;
50     while(tc--)
51     {
52         scanf("%d",&n);
53         init();
54         for(i=0;i<n-1;i++)
55         {
56             scanf("%d%d",&a,&b);
57             add(a,b);
58             deg[b]++;
59         }
60         for(i=1;i<=n;i++)
61         if(!deg[i])
62         break;
63         dfs(i,0);
64         /*for(i=0;i<2*n-1;i++)
65         {
66             printf("%d %d\n",lis[i],deep[i]);
67         }*/
68         scanf("%d%d",&a,&b);
69         min=N+5;
70         j=0;
71         if(firs[a]>firs[b])
72         {
73             a^=b;
74             b^=a;
75             a^=b;
76         }
77         for(i=firs[a];i<=firs[b];i++)
78         if(deep[i]<min)
79         {
80             min=deep[i];
81             j=lis[i];
82         }
83         printf("%d\n",j);
84     }
85     return 0;
86 }