LCA(最近公共祖先)

LCA(Least Common Ancestors)，即最近公共祖先，例如求两个节点u， v两个节点的最近的共同祖先我们可以用暴力、倍增、ST等方法解决

暴力

暴力法求解一对节点u和v的LCA时时间复杂度是O(n)的，所以当查询多对节点的LCA时，暴力算法的时间复杂度往往不满足要求。
暴力法就是通过不断地将深度较深的点往上求父节点，直到两个点的父节点重合时，即可得到LCA。

倍增

倍增法其实就是在暴力的基础上每一步尽可能跳的多一些，假设我们要求解lca(u,v)，暴力的想法是我们始终将深度较深的往上跳跃一步，直到u,v的深度第一次相等时，此时该节点就是lca(u,v)，但是这样做的话，时间复杂度是O(n）的，当有多组查询时，就容易超时。

倍增的原理是每一次尽可能地多跳一些步数，而不是一步一步往上跳，我们便可以选择跳跃2^j步进行尝试。

例题（倍增）：

洛谷P3379 【模板】最近公共祖先（LCA）

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 N,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 N−1 行每行包含两个正整数 x,y，表示 x 结点和 y 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 M 行每行包含两个正整数 a,b，表示询问 a 结点和 b 结点的最近公共祖先。

输出格式

输出包含 M 行，每行包含一个正整数，依次为每一个询问的结果。

思路：

设树中u、v两结点的最近公共祖先为lca(u,v)。用dfs求出他们的深度和父亲节点再在lca中倍增去不断(父亲不相等的话)的跳(2^j)

代码：

#include<bits/stdc++.h> using namespace std; int depth[500005] , father[500005][25] , n , m , s , x , y , a , b; vector<int> g[500005]; void dfs(int u , int fa){ father[u][0] = fa; for(int i = 1;i <= 20;i++){ father[u][i] = father[father[u][i - 1]][i - 1]; } depth[u] = depth[fa] + 1; for(int i = 0;i < g[u].size();i++){ int v = g[u][i]; if(v == fa){ continue; } dfs(v , u); } } int lca(int u , int v){ if(depth[u] < depth[v]){ swap(u , v); } for(int i = 20;i >= 0;i--){ if((depth[u] - depth[v]) >= (1 << i)){ u = father[u][i]; } } if(u == v) return u; for(int i = 20;i >= 0;i--){ if(father[u][i] != father[v][i]){ u = father[u][i]; v = father[v][i]; } } return father[u][0]; } int main(){ scanf("%d%d%d" , & n , &m , &s); for(int i = 1;i < n;i++){ scanf("%d%d" , &x , &y); g[x].push_back(y); g[y].push_back(x); } dfs(s , 0); for(int i = 1;i <= m;i++){ scanf("%d%d" , &a , &b); printf("%d\n" , lca(a , b)); } return 0; }