POJ1330(LCA)

Nearest Common Ancestors

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

思路

最近公共祖先(LCA)模板题，做法很多种就目前看到的做法有在线ST倍增；dfs + RMQ打表；离线的Tarjan。今天学的是倍增做法，打表复杂度是NlogN，单次查询的复杂度是logN。

1. 从根节点开始跑dfs，dfs的时候记录节点的深度 和 当前节点的父节点。
2. 对于当前访问的节点，倍增找到特殊的祖先节点，即跳跃：1（父亲），2（爷爷），4（爷爷的爷爷），8（爷爷的 爷爷的 爷爷）。也就是求出2 ^ 0，2 ^ 1，2 ^ 2…2 ^ log(n)的祖先。求的时候直接倍增，比如找爷爷的爷爷，可以通过爷爷去找他的爷爷。最后可以写出方程：
   f[x][i] = f[f[x][i-1]][i-1]。=> 2 ^ n = 2 ^ (n/2) * 2 ^ (n/2)。
3. 跑完dfs的时候，每个节点只存储了自己的特殊祖先，但是还是有很多普通祖先是没有存储的。比如跳3 = 2 ^ 0 + 2 ^ 1。虽然没有存跳3次的祖先，但是可以先让当前节点到父节点也就是先把那个单独的一次先跳了，再来倍增一次就到了。
4. 最后求最近公共祖先就简单了，假设给定两个点x 和 y，由于x 和 y深度可能不同，先让深度值大的节点利用结论3上跳abs(dep[x] - dep[y])次，然后两点深度相同。如果现在两个点是同一个值那么直接返回，如果不是同一个值对这两个点进行齐头并进的倍增，手牵手一起向上跳固定的次数。
5. 向上跳的次数从大到小枚举，先枚举大的深度值，再枚举小的。最后求出来的答案并不是直接的答案而是LCA的子节点。需要对任意一个子节点做f[x][0] 或者 f[y][0]得到答案。为什么从大到小枚举？为什么不能一次性求到答案？

自己的理解就是：因为一开始两点齐头并进一起跳的时候并不知道最近公共祖先是哪个，并不知道具体需要跳多少次，我们只能从大的范围开始搜跳到相同的值就不更新，不同的值再去更新两个节点的祖先值。也正是因为从大到小枚举才不能一次性求出答案，只能求出答案的子节点。假设前面遇到了很多个祖先a1，a2，a3，a4…an。那么an肯定是最近公共祖先，因为an的dfs深度值大，但是程序不知道an是最后一个公共祖先也是最近的公共祖先，那么程序肯定会错过它，但是没事，程序回把x 和 y 的值更新为an 的子节点。所以最后直接f[x][0] 或者 f[y][0]得到答案，可以针对下图模拟几次。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 10005;
const int maxd = 20;
vector<int>e[maxn];
int f[maxn][maxd];
int dep[maxn];
int in[maxn];
int n;

void clear_set()
{
	for(int i = 0;i < maxn;i++){
		e[i].clear();
	}
	memset(f,0,sizeof(f));
	memset(in,0,sizeof(in));
	memset(dep,0,sizeof(dep));
}

void dfs(int x,int fx)
{
	dep[x] = dep[fx] + 1;
	f[x][0] = fx;
	//子节点跳2^n次的父节点  ==>   先跳2^i/2  在跳  2^i/2 
	for(int i = 1;i < maxd;i++){
		f[x][i] = f[f[x][i-1]][i-1];    
	}
	for(int i = 0;i < e[x].size();i++){
		dfs(e[x][i],x);
	}
}

int LCA(int x,int y)
{
	if(dep[x] < dep[y])		swap(x,y);
	int d = dep[x] - dep[y];
	for(int i = 0;i < maxd;i++){		//调整到同一个高度 
		if(((1<<i) & d)){				//位运算，每次跳2的次方步 
			x = f[x][i];
		}
	}
	if(x == y)		return x;			//相同直接返回 
	for(int i = maxd-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;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		clear_set();
		int x,y;
		for(int i = 0;i < n-1;i++){
			scanf("%d%d",&x,&y);
			e[x].push_back(y);
			in[y]++;
		}
		int rt = 0;
		for(int i = 1;i <= n;i++){			//找到树根 
			if(in[i] == 0){
				rt = i;
			}
		}
		dfs(rt,0);
		scanf("%d%d",&x,&y);
		printf("%d\n",LCA(x,y));
	}
	return 0;
}

愿你走出半生，归来仍是少年~