LCA是啥？
在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。
换句话说，就是两个点在这棵树上距离最近的公共祖先节点。
------>例如，对于下面的树，结点4和结点6的最近公共祖先LCA(T,4,6)为结点2。
有什么方法？
暴力
tarjan
倍增
LCA转RMQ
树链剖分
欧拉序+RMQ
……（等等奇怪算法）
1.暴力
- 首先计算出结点u和v的深度d1和d2。如果d1>d2，将u结点向上移动d1-d2步，如果d1<d2，将v结点向上移动d2-d1步，现在u结点和v结点在同一个深度了。下面只需要同时将u，v结点向上移动，直到它们相遇（到达同一个结点）为止，相遇的结点即为u，v结点的最小公共祖先。
- 该算法时间复杂度为O(h)，对于多次询问的题目不能解决（这种方法一般20分）
2.倍增
- 倍增法其实是在暴力搜索的基础上进行了优化，我们希望向上查找更快，可以事先预处理出p[i,j]，表示i往上移动2^j步到达的结点，这样在查找时将大大节约时间。
- 由定义有
简单解释一下，p[i][j]是从i移动2^j步，相当于移动两次2^j步，第一次 p[ i ][ j-1 ] ,第二次 p[ p[i][j-1] ][ j-1 ]
- 利用P数组可以快速的将结点i向上移动n步，方法是将n表示为2进制数。比如n=6，二进制为110，那么利用P数组先向上移动4步(2^2)，然后再继续移动2步(2^1)，即P[ P[i][2] ][1]。
首先预处理出所有的p[i][j],并计算每个点的深度d[i]: void dfs(int u,int fa)//从根结点u开始dfs，u的父亲是fa { d[u]=d[fa]+1; //u的深度为它父亲的深度+1 p[u][0]=fa; //u向上走2^0步到达的结点是其父亲 for(int i=1;(1<<i)<=d[u];i++) p[u][i]=p[p[u][i-1]][i-1];//预处理p时，保证能从u走到p[u][i] for(int i=head[u];i!=-1;i=e[i].next)//对于u的每个儿子 { int v=e[i].v; if(v!=fa)dfs(v,u); //递归处理以v为根结点的子树 } } 在主函数中调用dfs(1,0)即可接下来是查询结点a,b的LCA
int lca(int a,int b) { if(d[a] > d[b]) swap(a , b) ; //保证a点在b点上面，d[a]<d[b] for(int j = 20 ; j >= 0 ; j--) //将b点向上移动到和a的同一深度 if(d[a] <= d[b] - (1<<j))
b = p[b][j] ; if(a == b) return a ;//如果a和b相遇 for(int j = 20 ; j >= 0 ; j--)//a,b同时向上移动 { if(p[a][j] == p[b][j]) continue ;//如果a,b的2^j祖先相同，则不移动 a = p[a][j] , b = p[b][j] ;//否则同时移动到2^j处 } return p[a][0] ;//返回最后a的父亲结点，为什么返回父亲节点呢？因为啊a,b同时向上移动时不会移动到祖先相同的节点，到最后就停留在我们要找的节点的儿子上。 }
#include<cstdio> #include<string> #include<iostream> using namespace std; const int maxn=500005; int n,m,s; struct edge{ int v,next; }e[maxn*2]; int head[maxn],cnt; int dep[maxn],f[maxn][21]; int read()//快读 { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } void add(int u,int v) //前向星建树 不会的https://www.cnblogs.com/mzyczly/p/11024914.html { e[++cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } void readdata() { n=read(),m=read(),s=read(); for(int i=1;i<=n-1;i++) { int a,b; a=read(),b=read(); add(a,b); add(b,a); } } void dfs(int u,int fa) //预处理 { dep[u]=dep[fa]+1; f[u][0]=fa; for(int i=1;(1<<i)<=dep[u];i++) f[u][i]=f[f[u][i-1]][i-1]; for(int i=head[u];i;i=e[i].next) { if(e[i].v!=fa) dfs(e[i].v,u); } } int lca(int a,int b) //查询LCA { if(dep[a]>dep[b]) swap(a,b); for(int i=20;i>=0;i--) { if(dep[a]<=dep[b]-(1<<i)) b=f[b][i]; } if(a==b) return a; for(int i=20;i>=0;i--) { if(f[a][i]==f[b][i]) continue; a=f[a][i],b=f[b][i]; } return f[a][0]; } void work() { dfs(s,0); for(int i=1;i<=m;i++) { int a,b; a=read(),b=read(); printf("%d ",lca(a,b)); } } int main() { readdata(); work(); return 0; }
时间复杂度分析
预处理：对每一个结点找到它向上走2^logN步到达的点，所以时间是NlogN
一组询问复杂度：O(logn)。
所以总复杂度为 O(NlogN+QlogN)（Q是询问次数）
空间复杂度：O(nlogn)。
3.LCA→RMQ的转化
RMQ是啥，看这。