LCA 最近公共祖先

1.倍增LCA 通过记录f[i][j],每个点第2的j次方个父亲的编号，来找LCA 代码中，先要处理出每个点的深度，和father（f[i][0]），然后倍增求出所有的祖先。 work的时候，利用二进制拆分的思想，先把两个节点向上翻到同一个深度，再同时向上翻，直到到了lca的儿子位置，再返回f[x][0]（f[y][0]）即可。 优点：容易理解，代码不难。 缺点：f数组空间较大，并且求法单一，难以与其他模型结合。 复杂度：每次O(logn)，多次O(mlogn) 核心部分： ```cpp int main() { for(int j=1;j<=L;j++) for(int i=1;i<=n;i++) { f[i][j]=f[f[i][j-1]][j-1]; } dep[0]=-1;//important!! for(int i=1;i<=n;i++) { int t=i; for(int j=L;j>=0;j--) if(f[t][j]!=0) { t=f[t][j]; dep[i]+=(1<<j); } } } int LCA(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int j=L;j>=0;j--) {if(dep[f[x][j]]>=dep[y]) x=f[x][j]; } if(x==y) return x; for(int j=L;j>=0;j--) if(f[x][j]!=f[y][j]) x=f[x][j],y=f[y][j]; return f[x][0]; } ``` 2.树链剖分LCA 常规树剖操作，两次dfs，找到top数组。 每次，将dep[top[]]较深的向上找到fa[top[]]，直到top[x]=top[y]为止。最后返回浅的位置编号。 优点：可以和树剖其他操作结合，找lca就是分分钟的事。 缺点：单纯lca代码量较大，（也不太大），记录东西较多，同意漏。 核心部分： ```cpp int fa[N],dep[N],son[N],top[N],size[N];//全部需要的数组 int work(int x,int y)//lca部分 { while(top[x]!=top[y]) { if(dep[top[x]]>dep[top[y]]) swap(x,y); y=fa[top[y]]; } if(dep[x]<dep[y]) swap(x,y); return y; } ``` 3.Tarjan LCA 利用tarjan的思想，通过并查集实现对子树的缩点，离线操作处理LCA问题。 用邻接表记录下询问信息之后，我们只需要从根节点开始处理，不停询问子树后回溯。边求边更新并查集fa的值。 向下循环的时候，每一个点被访问的时候，fa都是自己的编号。 当一棵子树被处理完了之后，这棵子树的fa就到了这棵树的根节点，以后还没有处理的lca，都至少已经是这个fa了。 处理子树x的时候，先循环与之有关的询问，如果y已经vis过了，就可以更新lca为fa[y]，因为x必然在fa[y]的子树中，且不在y所在的子树中。 之后向下循环，处理所有的儿子，回溯的时候，处理fa[y]=x; 这样复杂度就是线性的，每个询问被循环最多两次，每个子树被访问一次。 优点：复杂度低。O(n+m)。 缺点：必须离线操作。 复杂度：O(n+m) 代码核心： ```cpp void add2(int x,int y,int numb) { w[++tot].nxt=pre[x]; w[tot].to=y; w[tot].num=numb; pre[x]=tot; } int fin(int x) { if(fa[x]==x) return x; return fa[x]=fin(fa[x]); } void tarjan(int x) { fa[x]=x; vis[x]=1; for(int i=pre[x];i;i=w[i].nxt) { int y=w[i].to; if(vis[y]) lca[w[i].num]=fin(y); } for(int i=head[x];i;i=e[i].nxt) { int y=e[i].to; if(!vis[y]) { tarjan(y); fa[y]=x; } } } ``` 参考[Tarjan离线算法求最近公共祖先（LCA）](https://blog.csdn.net/csyzcyj/article/details/10051173) 应用： 多次查找树上两点之间的距离，可以预处理到根节点dis值。 dis[i][j]=dis[i]+dis[j]-2×dis[lca(i,j)]