首先，介紹何謂“最近公共祖先”，其實就是對于一顆二叉或者多叉樹來說，每個節點都有祖先節點（根節點除外），對于任意兩個點，a，b，它們可能有多個公共的祖先點c，即c為a的祖先且c為b的祖先，我們定義深度最大的那個公共祖先C為a，b的最近公共祖先，這個點是唯一的。
對于求最近公共祖先的算法有不少，著名的是LCA的線上算法和離線算法，看了這麼多網上的代碼，很少能找到我中意的，而且有些線上算法時間複雜度實在太高，是以我覺得有必要把自己想的一些東西拿出來給大家分享分享。
我們想想普通的方法來求a，b兩個點的最近公共祖先C：
View Code
int LCA(int a,int b)//求a，b的LCA
{
while(a!=b)//找到a,b的LCA
{
if(p[a].deep>p[b].deep)
{
a=p[a].father;
}
else
{
b=p[b].father;
}
}
return a;
} 意思就是一步一步向上尋找a，b點的父節點，知道找到他們的父節點相同，那麼此時的點就是點C；但是如果這棵樹很大，那麼這個算法實在太慢了，是以我們就優化這個地方。
我們來看看這樣一棵樹：
0 -------deep=0
/ \
1 2 -------deep=1
/ \
3 4 -------deep=2
/ \
5 6 ------deep=3
\
7 -------deep=4
我們以深度為界限把數分段，比如我把深度為0和1的點作為第一段，深度2和3的點作為第二段，然後檢視a和b是否在同一段，若不是同一段，則向上一段去尋找，直到a和b為同一段，然後再依照父節點去尋找最近公共祖先C：
View Code
int LCA(int a,int b)//求a，b的LCA
{
while(p[a].sec!=p[b].sec)//找到a，b亮點所在的段
{
if(p[a].deep>p[b].deep)
{
a=p[a].sec;
}
else
{
b=p[b].sec;
}
}
while(a!=b)//找到a,b的LCA
{
if(p[a].deep>p[b].deep)
{
a=p[a].father;
}
else
{
b=p[b].father;
}
}
return a;
} 代碼中p[u].sec為點u所歸屬的段，也就是歸屬的集合，也就是我們常說的并查集來分段。具體怎麼分，方法有很多，可以以一個分叉點到下一個分叉點之間的所有點作為一個集合，而且網上大多數算法都是這麼做的，這樣做起來最好的時間複雜度是o(lgn)，但是最複雜的情況将是o(n)。在這裡我介紹一種特殊的分段方法，最好和最複雜的時間複雜度都是o（sqrt(n)），即依照節點的深度deep來分段，每一段的長度為sqrt(max(deep))，比如一棵樹最大深度為100，那麼深度為1~9的點為集合0，深度10~19的點為集合1，依次類推。
補充：
當然如果我們這樣來分段，在下面的代碼中：
p[u].deep%sec==0；時，我們應該把p[u].sec=p[p[u].father].sec+1;但是這樣子的複雜度還是有點高，為了讓複雜度再降低，我們把段分的更多，也就是當p[u].deep>=sqrt(max(deep))的時候，我們把段标記為它的父節點，這樣深度相同的節點也可以在不同的段裡面，可以讓我們更快的查詢最近公共祖先。（這裡感謝一樓的提醒，一開始忘記說了） View Code
void setsection(int u,int sec)//建構點u屬于的段集合，每一段深度為sec
{
if(p[u].deep<sec)
{
p[u].sec=0;
}
else
{
if(p[u].deep%sec==0)
{
p[u].sec=p[u].father;
}
else
{
p[u].sec=p[p[u].father].sec;
}
}
for(unsigned i=0;i<p[u].next.size();i++)
{
int k=p[u].next[i];
if(p[k].father==u)
{
setsection(k,sec);
}
}
} 說到這裡，整個LCA的算法也就差不多講完了，并查集分段的方法無外乎這兩種，我的代碼是後者，畢竟還是比較好了解的，如果不懂也可以留言，下面我把全部的代碼都貼上來。
我們一開始給的是一個圖，但是我們要把這個圖變為一棵樹，以任意節點作為根節點建樹（此處以點0為root），建樹過程标記父節點和深度，然後給節點分段，最後可以做任意次數的查詢：
步驟：1.為圖建樹，标記節點的父節點和深度
2.為樹上的節點分段，使用并查集
3.直接查詢（a，b）兩個節點的LCA即可。
View Code
1 //====================================================================
2 //Name :LCA最近公共祖先
3 //Author :hxf
4 //copyright :http://www.cnblogs.com/Free-rein/
5 //Description:
6 //Data :2012.8.20
7 //========================================================================
8 #include<iostream>
9 #include<algorithm>
10 #include<stdio.h>
11 #include<math.h>
12 #include<string>
13 #include<cstring>
14 #include<vector>
15 #include<stack>
16 #include<queue>
17 #define MAXN 1040
18 #define inf 10100
19 #define pi 3.141592653589793239
20 using namespace std;
21 struct Tree{
22 vector<int> next;//子節點
23 int father;//父節點
24 int deep;//深度
25 int sec;//屬于的段
26 }p[50050];
27 int visit[50050];
28 int maxdeep;//最大深度
29 void dfs(int u)//建構多叉樹，找到父節點和深度
30 {
31 visit[u]=1;
32 for(unsigned i=0;i<p[u].next.size();i++)
33 {
34 int k=p[u].next[i];
35 if(visit[k]==0)
36 {
37 p[k].deep=p[u].deep+1;
38 p[k].father=u;
39 dfs(k);
40 }
41 }
42 maxdeep=max(maxdeep,p[u].deep);
43 }
44 void setsection(int u,int sec)//建構點u屬于的段集合，每一段深度為sec
45 {
46 if(p[u].deep<sec)
47 {
48 p[u].sec=0;
49 }
50 else
51 {
52 if(p[u].deep%sec==0)
53 {
54 p[u].sec=p[u].father;
55 }
56 else
57 {
58 p[u].sec=p[p[u].father].sec;
59 }
60 }
61 for(unsigned i=0;i<p[u].next.size();i++)
62 {
63 int k=p[u].next[i];
64 if(p[k].father==u)
65 {
66 setsection(k,sec);
67 }
68 }
69 }
70 void preLCA()
71 {
72 maxdeep=0;
73 dfs(0);
74 setsection(0,(int)sqrt(maxdeep));//每一段深度為sqrt(maxdeep)
75 }
76 int LCA(int a,int b)//求a，b的LCA
77 {
78 while(p[a].sec!=p[b].sec)//找到a，b亮點所在的段
79 {
80 if(p[a].deep>p[b].deep)
81 {
82 a=p[a].sec;
83 }
84 else
85 {
86 b=p[b].sec;
87 }
88 }
89 while(a!=b)//找到a,b的LCA
90 {
91 if(p[a].deep>p[b].deep)
92 {
93 a=p[a].father;
94 }
95 else
96 {
97 b=p[b].father;
98 }
99 }
100 return a;
101 }
102 int main()
103 {
104 int n;//n個節點
105 while(scanf("%d",&n)!=EOF)
106 {
107 for(int i=0;i<n;i++)
108 {
109 p[i].next.clear();
110 p[i].father=0;
111 p[i].deep=0;
112 p[i].sec=0;
113 }
114 for(int i=0;i<n-1;i++)
115 {
116 int x,y;
117 scanf("%d %d",&x,&y);
118 p[x].next.push_back(y);
119 p[y].next.push_back(x);//建邊
120 }
121 memset(visit,0,sizeof(visit));
122 preLCA();//建樹
123 ///
124 int m;//做m次查詢
125 scanf("%d",&m);
126 while(m--)
127 {
128 int a,b;
129 scanf("%d %d",&a,&b);
130 int lcaab=LCA(a,b);//得到a，b的LCA
131 printf("%d\n",lcaab);
132 }
133 }
134 return 0;
135 } 轉載于:https://www.cnblogs.com/Free-rein/archive/2012/08/24/2654519.html