LCA/在线(倍增)离线(Tarjan)
- 概念
- 祖先
- 公共祖先
- 最近公共祖先
- 方法1:暴力爬山法
- 方法2:倍增
- 求公共祖先
- 求俩点的距离
- Tarjan
概念
祖先
有根树中，一个节点到根的路径上的所有节点被视为这个点的祖先，包括根和它本身
公共祖先
对于点a和b，如果c既是a的祖先又是b的祖先，那么c是a和b的公共祖先
##深度
子节点的深度=父节点深度+1，一般我们定根的深度为1
最近公共祖先
树上两个节点的所有公共祖先中，深度最大的那个称为两个点的最近公共祖先(LCA)
方法1:暴力爬山法
很明显，这个方法是很想爬山，我们可以先然两个节点中，深度大的依着父亲爬到两节点深度相同，然后，两个节点一起爬，最后，爬到了同一个节点，这，就是ans；
很明显，这个方法有几个缺陷，时间为O（n）,并且，还要用bfs算深度
方法2:倍增
求公共祖先
在前面爬山法进行改进，在爬山的过程中，其实有些地方可以一蹦千尺高，但却一步一步地走，大大的浪费了时间，于是，我们运用倍增
众所周知，任意一个数是可用二进制来表示，如果，我们用一个二进制来表示两个节点的深度差，那不是就把时间化为O（log2n）
设一个数组dp[i][j]从i这个节点往上走2j步，那么，dp[i][j-1]j就是再往根的方向走2(j-1)步，如果再走2(j-1)步,就相当于走了2j，所以，dp[i][j]=dp[dp[i][j-1]][j-1]
其中，dp[i][0]=fa[i];
那如何来求dp这个数组呢
我们可以在bfs求树上每个点深度的时候，顺便预处理dp数组
void bfs()
{
queueq;
d[root]=1;
q.push(root);
while(q.size())
{
int temp=q.front();
q.pop();
for(int i=0;i LCA就是在爬山的基础上，将一步一步的枚举，改为，从大到小走2j
int LCA(int a, int b) {
if (d[a] > d[b]) {
swap(a, b);
}
for (int i = Maxstep; i >= 0; i--) {
if (d[dp[b][i]] >= d[a]) {
b = dp[b][i];
}
}
if (a == b) {
return a;
}
for (int i = Maxstep; i >= 0; i--) {
if (dp[b][i] != dp[a][i]) {
a = dp[a][i];
b = dp[b][i];
}
}
return dp[a][0];
}
求俩点的距离
可以先求出两点的LCA，然后，这两点的距离，就是公共祖先到A的距离+公共祖先到B的距离，而距离，可以和算深度一样，算到根节点的距离
int dist(int x, int y) { return d[x] + d[y] - d[LCA(x, y)] * 2; }
Tarjan
离线的求LCA的方法
先dfs，然后，标记，用并查集的路径压缩记录这个节点，最近的，没有回溯的节点，如果，询问的两个节点中有被访问的，那就可以将这个结点并查集的祖先放进去，正因为这样，所以，所有的，都需要先放进去，在dfs
void Trajan(int x) {
vis[x] = 1;
for (int i = 0; i < g[x].size(); i++) {
int v = g[x][i];
if (vis[v]) {
continue;
}
Trajan(v);
fa[v] = x;
}
for (int i = 0; i < q[x].size(); i++) {
int ID = q[x][i].id;
if (vis[q[x][i].v] == 1) {
ans[ID] = find(q[x][i].v);
}
}
}