解决问题：

·祖先：有根树中，一个节点到根的路径上的所有节点被视为这个点的祖先，包括根和它本身 ·公共祖先：对于点a和b，如果c既是a的祖先又是b的祖先，那么c是a和b的公共祖先 ·深度：子节点的深度=父节点深度+1，一般我们定根的深度为1 ·最近公共祖先：树上两个节点的所有公共祖先中，深度最大的那个称为两个点的最近公共祖先(LCA) **

解决方法

1. 暴力

1.如果a和b的深度不同，那么将深度更大的那个点向根的方向移动一步，即选择它的父节点，重复这个过程直到两个点深度相同 2.当a和b深度相同，但不是同一个点，那么各自向根的方向移动一步，即选择它们各自的父节点，重复这过程直到选择到同一个点

int LCA(int x, int y) { while(d[a] != d[b]) { if(d[a] > d[b]) b = f[b]; else a = f[a]; } while(a != b) { a = f[a]; b = f[b]; } return a; }

可以看到这种方法是一个一个向上找，如果是线性的话就会退化成O(n) 加上查找数量一般都会超时 那么就隆重地介绍一下，下面的算法树上倍增。

2.倍增

先求出每个点往根的方向走2的幂步的点，和快速幂中求a的次方类似。 如果我们以dp[i][j]表示从i往根方向走2^{j步的节点，那么也就等于从dp[i][j-1]再往根的方向走2}(j-1)步的结果，即dp[i][j]=dp[fa[i][j-1]][j-1]。 可以在bfs求树上每个点深度的时候，顺便预处理dp数组，时间复杂度o(nlogn)。 一般如果走的步数超过到根的步数，一般设结果为0，因为一般点的编号不包括0

void bfs() { q.push(root); dis[root] = 1; while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x]; i; i = next[i]) { int t = to[i]; if(dis[t]) continue; dis[t] = dis[x] + 1; dp[t][0] = x; for(int j = 1; j <= maxstep; j ++) { dp[t][j] = dp[dp[t][j - 1]][j - 1]; } q.push(t); } } }

那么如何查找呢，也可以使用倍增，为了方便先使y > x(深度），考虑往根的方向走2^i步之后深度会不会小于x的深度，如果不会就选择走，反之就选择不走，当深度相同时可以先判断一下是否相等，如果是就返回，不是就同时向上查找（注：if语句只会使x,y到达公共祖先的字节点所以要返回x或y的父亲）

int lca(int x, int y) { if(dis[x] > dis[y]) swap(x, y); for(int i = maxstep; i >= 0; i --) { if(dis[dp[y][i]] >= dis[x]) { y = dp[y][i]; } } if(x == y) return x; for(int i = maxstep; i >= 0; i --) { if(dp[x][i] != dp[y][i]) { x = dp[x][i]; y = dp[y][i]; } } return dp[x][0]; }

接下来贴完整代码（不带权值）

#include<cmath> #include<queue> #include<cstdio> #include<algorithm> using namespace std; queue<int> q; int cnt, maxstep, dis[100005], dp[100005][105]; int head[200005], to[200005], next[200005], root; void add(int x, int y) { to[++ cnt] = y; next[cnt] = head[x]; head[x] = cnt; } void bfs() { q.push(root); dis[root] = 1; while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x]; i; i = next[i]) { int t = to[i]; if(dis[t]) continue; dis[t] = dis[x] + 1; dp[t][0] = x; for(int j = 1; j <= maxstep; j ++) { dp[t][j] = dp[dp[t][j - 1]][j - 1]; } q.push(t); } } } int lca(int x, int y) { if(dis[x] > dis[y]) swap(x, y); for(int i = maxstep; i >= 0; i --) { if(dis[dp[y][i]] >= dis[x]) { y = dp[y][i]; } } if(x == y) return x; for(int i = maxstep; i >= 0; i --) { if(dp[x][i] != dp[y][i]) { x = dp[x][i]; y = dp[y][i]; } } return dp[x][0]; } int main() { int T, n, m, x, y, s; scanf("%d %d", &n, &m); maxstep = (int)log(n) / log(2) + 1; for(int i = 1; i <= n - 1; i ++) { scanf("%d %d", &x, &y); add(x, y); add(y, x); } root = 1; bfs(); for(int i = 1; i <= m; i ++) { scanf("%d %d", &x, &y); printf("%d\n", lca(x, y)); } }

其实还有很多方法这里就不一一介绍啦（因为懒）拜拜~~