M05804: 公共祖先

http://cs101.openjudge.cn/practice/05804/

完全二叉树的定义如下：除最后一层外其它各层的节点都是满的，并且最后一层都连续集中在最左边。如下图

一个节点从自己开始沿父节点方向走到树的根节点，中间途径的所有节点称为该节点的祖先节点。

节点12的祖先依次是12、6、3、1，节点5的祖先依次是5、2、1。

给出若干个节点，找出它们编号最大的公共祖先。

输入

第一行输入一个整数t，表示测试数据的个数。对于每组测试数据，第一行输入一个整数n，代表节点个数。随后的第二行输入n个整数，代表n个节点的编号， 1<=n<=10 , 每个节点编号的取值范围[1,10000]。

输出

对于每组测试数据，输出这些节点最大的公共祖先。

样例输入

样例输出

2
1
2

提示

本题不需要去建立一颗真实的二叉树。仅考查完全二叉树的一个基本性质。应用题目中所说的子节点与父节点编号关系就可以解决本题，即“对于一个编号为i的节点，其父节点是[i/2]，[x]代表给x向下取整”。解题思路如下：

以找两个节点45、17的公共祖先为例， 45的祖先节点依次为：45、22、11、5、2、1。所以从树的根节点开始到45号节点的路径为： 1 -> 2 -> 5 -> 11 -> 22 17的祖先节点依次为：17、8、4、2、1。所以从树的根节点开始到17号节点的路径为： 1 -> 2 -> 4 -> 8 -> 17 两个序列最后的公共元素2便是45和17号节点编号最大的公共祖先节点。

多个节点的情况可以转换成两个节点的情况，比如5个节点A1，A2，A3，A4，A5：先找到A1，A2的最大公共祖先节点f( A1 , A2 ) 然后找A3与f(A1,A2)的最大公共祖先节点f( f(A1 , A2) , A3 ) …… 程序始终只需要找两个节点的最大公共祖先节点。

这个问题利用了完全二叉树的一个核心性质：对于任意编号为 $i$ 的节点，其父节点的编号为 $⌊ i / 2 ⌋$ （即 $i$ 向下取整除以 2）。

解题思路

找两个节点的 LCA：由于父节点编号总是比子节点小，我们可以让编号较大的那个节点不断地“向上爬”（即 node //= 2），直到两个节点的编号相等为止。此时相遇的编号就是它们的最近公共祖先。
找多个节点的 LCA：我们可以使用递推的思想。先找前两个节点的 LCA，得到的结果再与第三个节点找 LCA，以此类推。例如：LCA(a, b, c) = LCA(LCA(a, b), c)。
Python 代码实现

python

import sys

def find_lca_of_two(a, b):
    """查找两个节点 a 和 b 的最近公共祖先"""
    while a != b:
        if a > b:
            a //= 2  # 较大者向上爬
        else:
            b //= 2  # 较大者向上爬
    return a

def solve():
    # 使用 sys.stdin.read().split() 处理所有空格/换行符分割的输入
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    ptr = 0
    t_str = input_data[ptr]
    ptr += 1
    t = int(t_str)
    
    for _ in range(t):
        n = int(input_data[ptr])
        ptr += 1
        
        # 读取当前组的 n 个节点
        nodes = []
        for _ in range(n):
            nodes.append(int(input_data[ptr]))
            ptr += 1
            
        if not nodes:
            continue
        
        # 迭代处理：先取第一个数作为初始 LCA，然后不断与后面的数求 LCA
        res_lca = nodes[0]
        for i in range(1, n):
            res_lca = find_lca_of_two(res_lca, nodes[i])
        
        # 输出结果
        print(res_lca)

if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：对于每个节点，向上爬到根节点最多需要 $\log_{2} (10000) \approx 14$ 步。总复杂度为 $O (T \times N \times \log (MaxID))$ 。在本题数据范围内（ $N \leq 10$ , $I D \leq 10000$ ），运行速度极快。
空间复杂度： $O (N)$ ，用于存储当前测试用例的节点。

M05804: 公共祖先 ​

M05804: 公共祖先