Data Structure: LCA

LCA: （Lowest Common Ancestor）最近公共祖先问题

Introduction

什么是公共祖先问题？我们进行问题重述：

给定一棵有根树$T$，考虑两个节点$u$，$v$，则要求找出树中的一个节点$target=LCA(T,u,v)$，使节点$target$满足：

• $target$是节点$u$和$v$的公共祖先。
• 在满足性质1的条件下，要求**$target$的深度尽可能的深（即离根节点尽可能的远，离两个节点尽可能的近）**。

对于该问题，我们需要对一棵节点数为$N$的树进行$M$次询问。

朴素解法

解决单次询问并不是很难的一件事，我们可以在$O(h)\le O(N)$的时间复杂度下完成。

首先，我们需要移动两个节点到同一深度，即$height$相同。接下来需要两个节点不断完成找爸爸的操作，找到第一个相遇的点即为所求。

显然，对于最坏的情况，（比如一棵严重退化的树），完成$M$次查询的复杂度是$O(MN)$。

倍增优化

如何优化？我们先把两个节点调整到相同的高度。由于我们计算的是最近公共祖先问题，我们显然知道：如果$S$是最近公共祖先，那么$S$的所有祖先节点肯定也都是满足条件1的公共祖先！因此，如果把是不是一个公共祖先定义为一个bool值，那么这明显是一个单调递减的序列（$111..10000..00$）,我们可以使用二分查找的方式来找到最终的答案，二分查找本身的复杂度是$O(\log n)$。

但是这样存在一个问题，我们需要在低于线性时间复杂度内知道每一个节点向上跳n次会调到哪一个节点，即$upd(u,d)$，$u$是节点，$d$是向上跳的层数，最终返回一个节点值。我们需要进行预处理，来实现这个函数的高效运算。

如何预处理？倍增法！（因为这不是一个可重复性贡献问题），我们可以使用$fa[u][i]$代表$upd(u,d=2^i)$的值，然后使用倍增法拼起来，这样就可以实现每次查询$O(\log n)$的时间复杂度。对于预处理的过程，可以直接使用深度优先搜索，在预处理好祖先节点的时候，使用动态规划就计算当前节点的预处理的值，并且继续递归处理当前节点的子节点。

代码如下：

▶

TOBEDONE

别看了，这没写完，快去写作业叭。

使用倍增法，我们可以实现在预处理过后单次查询的复杂度是$O(\log ^2 (n))$,同时，既然我们已经使用了倍增算法，就不必再二分查找了，我们可以从大到小枚举$2^i$，如果不一样就直接跳，一样就不要动，这样也可以在$O(\log n)$的时间内完成查询操作。

最终我们实现算法的复杂度如下：

• 预处理查询：$O(n\log n)$
• $M$次查询：$O(M\log n)$

欧拉序

在介绍欧拉序之前先介绍一下DFS序：

树的DFS序列，也就是树的深搜序，它的概念是：树的每一个节点在深度优先遍历中进出栈的时间序列。

具体来说，在DFS序列中，每一个节点会出现两次，分别代表入队时刻和出队时刻，即开始探索这个节点和探索完毕离开这个节点（递归：探索完毕这个节点的所有子节点）。例如我们可以有如下的代码：

/*
implementation of DFS search
*/

#include <iostream>
#include <vector>

class Tree {
private:
    std::vector<std::vector<int>> adjList; // Adjacency list representation of the tree
    std::vector<int> dfsOrder;            // Stores the DFS order

    // Helper function for DFS traversal
    void dfs(int node, int parent) {
        dfsOrder.push_back(node); // Add the current node to the DFS order (entering the node)

        // Visit all children of the current node
        for (int child : adjList[node]) {
            if (child != parent) { // Avoid revisiting the parent node
                dfs(child, node);
            }
        }

        dfsOrder.push_back(node); // Add the current node to the DFS order again (leaving the node)
    }

public:
    // Constructor to initialize the tree with n nodes
    Tree(int n) {
        adjList.resize(n + 1); // Nodes are 1-indexed
    }

    // Add an edge to the tree
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u); // Since it's an undirected tree
    }

    // Perform DFS and return the DFS order
    std::vector<int> getDFSOrder(int root) {
        dfsOrder.clear(); // Clear any previous DFS order
        dfs(root, -1);    // Start DFS from the root node
        return dfsOrder;
    }
};

int main() {
    // Create a tree with 7 nodes
    Tree tree(7);

    // Add edges to the tree
    tree.addEdge(1, 2);
    tree.addEdge(1, 3);
    tree.addEdge(2, 4);
    tree.addEdge(2, 5);
    tree.addEdge(3, 6);
    tree.addEdge(3, 7);

    // Get the DFS order starting from node 1
    std::cout << "DFS Order (with enter and leave) starting from node 1:" << std::endl;
    std::vector<int> dfsOrder = tree.getDFSOrder(1);

    // Print the DFS order
    for (int node : dfsOrder) {
        std::cout << node << " ";
    }
    std::cout << std::endl;

    return 0;
}

DFS Order (with enter and leave) starting from node 1:
1 2 4 4 5 5 2 3 6 6 7 7 3 1 

这棵树长这样：

graph TD
    1[1] --> 2[2]
    1[1] --> 3[3]
    2[2] --> 4[4]
    2[2] --> 5[5]
    3[3] --> 6[6]
    3[3] --> 7[7]

我们来观察这个序列，会发现重要的性质：选择DFS序中那个$u$开始，$u$结束的子序列中长度一定是偶数，并且所有涉及的节点全部是u的子孙节点。换句话说DFS序的最大作用就是把复杂的树状结构转化成方便处理的线性结构。

在介绍完DFS序列之后，我们就可以介绍欧拉序列了，欧拉序的定义是：从根节点出发到回到根节点为止，按深度优先遍历的顺序所经过的所有点的顺序。欧拉序在顺序上反映了在遍历一棵树的时候向下递归和回溯的具体路径。

例如下面的树：

// Add edges to the tree
tree.addEdge(1, 2);
tree.addEdge(1, 3);
tree.addEdge(2, 4);
tree.addEdge(2, 5);
tree.addEdge(3, 6);
tree.addEdge(3, 7);
tree.addEdge(4, 8);
tree.addEdge(6, 9);
tree.addEdge(6, 10);

其DFS序和欧拉序的顺序如下：

DFS Order (with enter and leave) starting from node 1:
1 2 4 8 8 4 5 5 2 3 6 9 9 10 10 6 7 7 3 1 
Euler Order starting from node 1:
1 2 4 8 4 2 5 2 1 3 6 9 6 10 6 3 7 3 1 

欧拉序的长度为$2n-1$，而DFS序的长度为$2n$，因为每个点在欧拉序中出现的次数等于这个点的度数（该节点的子孙节点数量），因为DFS到的时候加进一次，回去的时候也加进。

观察欧拉序，我们很容易发现：给定两个节点$u$，$v$，从$u$到$v$的欧拉序路径上一定会经过最近公共祖先，并且只会经过一次！（而且其他的公共祖先都不会出现）。我们巧妙的利用DFS的性质实现从树结构到线性结构的转化。也就是说，我们只需要求一段区间中深度最小的点就是LCA!

这样，通过一次欧拉序变化，我们将求LCA问题转化为经典RMQ问题！

对于RMQ问题，可以使用ST表等内容解决。（因为是可重复性贡献问题）

代码如下：

▶

TOBEDONE

别看了，这没写完，快去写作业叭。

最终我们实现的算法复杂度如下：

• 预处理求欧拉序数组：$O(n)$
• 预处理求ST表：$O(n\log n)$
• M次查询，每一次都是$O(1)$的常数时间复杂度。

因此整体时间复杂度为$O(n\log n+M)$。

RMQ问题也可以转化成LCA问题来解决，将原序列转化为对应的笛卡尔树即可。

Applications

树上差分问题