LCA
\(\textbf{LCA=Lowest Common Ancestor}\)
即最近公共祖先
下文以 \(\textbf{LCA(a,b)表示节点a与节点b的最近公共祖先}\)
F1: 暴力算法
步骤：
（1）求出每个节点的深度（\(size\)）
（2）询问两个点是否重合，若重合，则\(\textbf{LCA(a,b)=当前重合的节点}\)
（3）否则，选择 \(\textbf{max(size[a],size[b])}\) 并移动到他的父亲节点
F2：倍增写法
倍增写法是基于F1暴力写法的优化版本，改进了时间复杂度
步骤：
（1）定义倍增数组 \(LCA[MAXN][MAXNLOG]\) ,其中 \(LCA[i][j]\) 表示 \(i\) 节点向上减少 \(2^j\) 步可到达的节点
因为想要跳 \(2^j\) 步可以先网上跳 \(2^{j-1}\) 步然后再站在 \(2^{j-1}\) 的地方再跳 \(2^{j-1}\) 步
由上可得公式：
\(\textbf{LCA[i][j]}\) = \(\textbf{LCA[ LCA[i][j-1] ][ j-1 ]}\)
即
\(2^j\) = \(2^{j-1}\) + \(2^{j-1}\)
（2）把\(a,b\) 移动到同一深度，即\(\textbf{size[a]==size[b]}\)
设\(maxab=max(size[a],size[b])\) ，\(minab=min(size[a],size[b])\)
则我们将\(maxab\)向上跳\(\textbf{size[minab]-size[maxab]}\) 步
并将这个步数表示成二进制，即 \(2^n\) 步，其中
n=\(log_2^{size[minab]-size[maxab]}\)
由此即可通过 倍增数组 ( LCA[MAXN] [MAXLOG] ) 来向上跳 \(2^i\) 步
即可实现在时间复杂度为 \(O(log_2^n)\) 的情况下到达目标深度
（3）求出 \(LCA(a,b)\)
设 \(L\) 为 \(a\) 与 \(b\) 节点向上走的第 \(L\) 步后到达了同一节点，则此节点就是 \(LCA(a,b)\)
同理，节点 \(a\) 与 \(b\) 向上走的第 \(L-1\) 步肯定为不同的节点
反之，向上走的第 \(L+1\) 步就为节点 \(a\) 与节点 \(b\) 第二近公共祖先，次公共祖先
我们可以从大到小枚举往上走 \(2^i\) 步，若节点 \(a\) 与 \(b\) 为同一节点则停止，否则一起向上走，直到根节点
算法代码：
int size[MAXN],LCA[MAXN][MAXLOG];
int fi[MAXN];//节点的后代个数
int to[MAXN];//节点的具体每个儿子
int nxt[MAXN];//nxt[i]表示节点i最后一条连出去的边
void dfs(int a,int father)
{
size[a]=size[father]+1;//子节点深度是父亲节点深度+1
LCA[a][0]=fa;//a节点向上走2^0 步为其父亲节点
for(int i=1;i<MAXLOG;i++)
{
LCA[a][i]=LCA[LCA[a][i-1]][i-1];//刚推的公式
}
for(int i=fi[a];i!=0;i=nxt[i])//类似于最短路中的链式向前星
{
if(to[i]!=father)
{
dfs(to[i],a);//递归调用
}
}
return;
}
int getLCA(int x,int y)
{
if(size[x]<size[y])//刚才我们是定义了maxab和minab,这里直接进行比较，选出深度较大的节点
{
swap(x,y);
}
for(int i=MAXLOG-1;i!=0;i--)
{
if(size[LCA[x][i]]>=size[y])
{
x=size[x][i];
}
}
if(x==y)
{
return x;//找到LCA了
}
for(int i=MAXLOG-1;i!=0;i--)
{
if(LCA[x][i]!=LCA[y][i])
{
x=LCA[x][i];
y=LCA[y][i];
}
}
return LCA[x][0];
}
F3：Tarjan 算法
步骤：
（1）使用 DFS 深搜整棵树，开始时每个节点都是一个独立的集合（ 并查集 ）
（2）DFS （x）时，每次访问完子树 y ,把集合 y 合并到 x 中
（3）当 x 的所有子节点都被访问结束后，标记 x 为 \(true\)，即已被访问
（4）遍历所有关于 x 的询问 \((x,y)\) ，如果 y 已被访问，则本访问答案为并查集的\(find(y)\)
代码实现：
string g[MAXN],q[MAXN];
int f[MAXN];
bool book[MAXN];
void init()
{
for(int i=1;i<=n;i++)
{
f[i]=i;
}
return;
}
int findfather(int x)
{
if(x==f[x])
{
return x;
}
f[x]=findfather(x);
return f[x];
}
void Union(int x,int y)//合并函数，将节点x所在的集合合并到集合y中
{
f[findfather(x)]=f[findfather(y)];
return;
}
void dfs(int x)
{
for(int i=0;i<g[x].size();i++)
{
dfs(g[x][i]);
Union(g[x][i],x);
}
book[x]=true;
for(int i=0;i<q[x].size();i++)
{
int m=q[]
}
return;
}