Nearest Common Ancestors
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 14078 Accepted: 7510
Description
A rooted tree is a well-known data structure in computer science and engineering. An example is shown below:
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
The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are 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
Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor.
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
Taejon 2002
在線算法 倍增法
每次詢問O(logN)
d[i] 表示 i節點的深度, p[i,j] 表示 i 的 2^j 倍祖先
那麼就有一個遞推式子 p[i,j]=p[p[i,j-1],j-1]
這樣子一個O(NlogN)的預處理求出每個節點的 2^k 的祖先
然後對於每一個詢問的點對a, b的最近公共祖先就是：
先判斷是否 d[a] > d[b] ,如果是的話就交換一下(保證 a 的深度小於 b 方便下面的操作)然後把b 調到與a 同深度, 同深度以後再把a, b 同時往上調(dec(j)) 調到有一個最小的j 滿足p[a,j]!=p[b,j] (a b 是在不斷更新的), 最後再把 a, b 往上調 (a=p[a,0], b=p[b,0]) 一個一個向上調直到a = b, 這時 a or b 就是他們的最近公共祖先
http://poj.org/problem?id=1330
【分析】
倍增法求LCA的大體思路：
首先確定深度d[i]，表示i到根節點的距離或者說是深度。
p[i,j]表示i向上的第2^j個祖先，則p[i,j+1]:=p[p[i,j],j];
dfs求出d[i]和p[i,j]。
如果求的是x和y的lca。那麼如果x=y，lca=x or y;
如果x和y的深度不同，則調整到同一深度，以便求lca。
x和y的深度相同了，就開始向上走，如果兩個點同時走了相同的步數，走到了一個點，那麼這個點就是lca，自己想象一下，這是顯然的事。兩個點最早到達的相同點不是lca是什麼= =
結束。
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define N 10010
#define M 20
int d[N],f[N][M];
vector<int>ch[N];
void dfs(int x){//求出所有結點深度
d[x]=d[f[x][0]]+1;
for(int i=1;i<M;i++)f[x][i]=f[f[x][i-1]][i-1];//倍增祖先
for(int i=ch[x].size()-1;i>=0;i--)
dfs(ch[x][i]);//遍歷兒子
}
int lca(int x,int y){//求x,y最小公共祖先
if(d[x]<d[y])swap(x,y);//保證x的深度不小於y
int k=d[x]-d[y];
for(int i=0;i<M;i++)
if((1<<i)&k)
x=f[x][i];
if(x==y)return x;//x==y時為最小公共祖先
for(int i=M-1;i>=0;i--)
if(f[x][i]!=f[y][i]){
x=f[x][i];y=f[y][i];
}
return f[x][0];
}
int main(){
int T,n,i,x,y;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(d,0,sizeof(d));
memset(f,0,sizeof(f));
memset(ch,0,sizeof(ch));
for(i=1;i<n;i++){
scanf("%d%d",&x,&y);
ch[x].push_back(y);
f[y][0]=x;
}
for(i=1;i<=n;i++)
if(f[i][0]==0){//找到根遍歷
dfs(i);break;
}
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define N 10010
#define M 20
int d[N],f[N][M];
vector<int>ch[N];
void dfs(int x){//求出所有結點深度
d[x]=d[f[x][0]]+1;
for(int i=1;i<M;i++)f[x][i]=f[f[x][i-1]][i-1];//倍增祖先
for(int i=ch[x].size()-1;i>=0;i--)
dfs(ch[x][i]);//遍歷兒子
}
int lca(int x,int y){//求x,y最小公共祖先
if(d[x]<d[y])swap(x,y);//保證x的深度不小於y
int k=d[x]-d[y];
for(int i=0;i<M;i++)
if((1<<i)&k)
x=f[x][i];
if(x==y)return x;//x==y時為最小公共祖先
for(int i=M-1;i>=0;i--)
if(f[x][i]!=f[y][i]){
x=f[x][i];y=f[y][i];
}
return f[x][0];
}
int main(){
int T,n,i,x,y;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(d,0,sizeof(d));
memset(f,0,sizeof(f));
memset(ch,0,sizeof(ch));
for(i=1;i<n;i++){
scanf("%d%d",&x,&y);
ch[x].push_back(y);
f[y][0]=x;
}
for(i=1;i<=n;i++)
if(f[i][0]==0){//找到根遍歷
dfs(i);break;
}
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
