倍增求LCA：
father【i】【j】表示节点i往上跳2^j次后的节点
可以转移为
father【i】【j】=father【father【i】【j-1】】【j-1】
整体思路：
先比较两个点的深度，如果深度不同，先让深的点往上跳，浅的先不动，等两个点深度一样时，if 相同 直接返回，if 不同 进行下一步；如果不同，两个点一起跳，j从大到小枚举（其实并不大），如果两个点都跳这么多后，得到的点相等，两个点都不动（因为有可能正好是LCA也有可能在LCA上方），知道得到的点不同，就可以跳上来，然后不断跳，两个点都在LCA下面那层，所以再跳1步即可，当father【i】【j】中j=0时即可，就是LCA，返回值结束
（摘自http://blog.csdn.net/dad3zz）
在网络海洋中搜寻很久后找到hzwer的宽搜求deep序，进行了学习。
以下是我的模板代码：
构造访问数组！
void make_bin()
{
bin[0]=1;
for(int i=1;i<=15;i++)
bin[i]=bin[i-1]<<1;
}
简明易懂邻接表！
void Link()
{
for(int i=1;i<=n-1;i++){//n-1 edges;or you can define a m pointing to the number of edges;
scanf("%d%d",&u[i],&v[i]);
u[i+n-1]=v[i];v[i+n-1]=u[i];//双向;
next[i]=first[u[i]];
next[i+n-1]=first[v[i]];//双向;
first[u[i]]=i;
first[v[i]]=i+n-1;//双向;
isroot[v[i]]=true;
}
}
宽搜！
void bfs()
{
int head=0,tail=1;
q[0]=root,vis[root]=true;
while(head^tail){
int now=q[head];head++;
for(int i=1;i<=15;i++){
if(bin[i]<=deep[now])
fa[now][i]=fa[fa[now][i-1]][i-1];
else break;
}
for(int i=first[now];i;i=next[i])
if(!vis[v[i]]){
vis[v[i]]=true;
fa[v[i]][0]=now;
deep[v[i]]=deep[now]+1;
q[tail++]=v[i];
}
}
}
求lca()
int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
for(int i=0;i<=15;i++)
if(t&bin[i])x=fa[x][i];
for(int i=15;i>=0;i--)
if(fa[x][i]^fa[y][i])
x=fa[x][i],y=fa[y][i];
if(!(x^y))return y;
return fa[x][0];
}
之后，在poj上找了一个众所周知的例题，poj1330，当做lca入门题
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 24757 | Accepted: 12864 |
Description
In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor
of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node
x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common
ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.
For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest
common ancestor of y and z is y.
Write a program that finds the nearest common ancestor of two distinct nodes in a tree.
Input
labeled with integers 1, 2,..., N. Each of the next N -1 lines contains a pair of integers that represent an edge --the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test
case contains two distinct integers whose nearest common ancestor is to be computed.
Output
Sample Input
2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5
Sample Output
4
3
Source
Source Code
| Problem: 1330 | User: ksq2013 | |
| Memory: 1224K | Time: 32MS | |
| Language: C++ | Result: Accepted |
ac代码如下：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
bool vis[10100],isroot[10100];
int root,q[10100],deep[10100],fa[10100][20];
int n,bin[20],first[10100],next[10100],u[10100],v[10100];
void make_bin()
{
bin[0]=1;
for(int i=1;i<=15;i++)
bin[i]=bin[i-1]<<1;
}
void Link()
{
for(int i=1;i<=n-1;i++){
scanf("%d%d",&u[i],&v[i]);
//u[i+n-1]=v[i];v[i+n-1]=u[i];
next[i]=first[u[i]];
//next[i+n-1]=first[v[i]];
first[u[i]]=i;
//first[v[i]]=i+n-1;
isroot[v[i]]=true;
}
for(int i=1;i<=n;i++)
if(!isroot[i]){
root=i;
break;
}
}
void bfs()
{
int head=0,tail=1;
q[0]=root,vis[root]=true;
while(head^tail){
int now=q[head];head++;
for(int i=1;i<=15;i++){
if(bin[i]<=deep[now])
fa[now][i]=fa[fa[now][i-1]][i-1];
else break;
}
for(int i=first[now];i;i=next[i])
if(!vis[v[i]]){
vis[v[i]]=true;
fa[v[i]][0]=now;
deep[v[i]]=deep[now]+1;
q[tail++]=v[i];
}
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
for(int i=0;i<=15;i++)
if(t&bin[i])x=fa[x][i];
for(int i=15;i>=0;i--)
if(fa[x][i]^fa[y][i])
x=fa[x][i],y=fa[y][i];
if(!(x^y))return y;
return fa[x][0];
}
int main()
{
make_bin();
int T;
scanf("%d",&T);
for(;T;T--){
memset(vis,false,sizeof(vis));
memset(isroot,false,sizeof(isroot));
memset(q,0,sizeof(q));
memset(fa,0,sizeof(fa));
memset(deep,0,sizeof(deep));
memset(first,0,sizeof(first));
memset(next,0,sizeof(next));
scanf("%d",&n);
Link();
bfs();
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}