最近祖先 题目描述 小科知道小丁和自己有亲缘关系，但是他不知道他们具体的亲缘关系，于是他打开家谱想要找到答案，但是家谱太庞大了，没看一会小科已经头昏眼花了，你可以帮助小科找到他和小丁的最近的公共祖先吗？为简化计算可以将小科的家谱看作是一个树形结构，树中的每个结点都有一个编号（1-n)。 输入格式 第1行：n, m, k, d，n表示家谱树中结点的数量，m表示树中关系的数量，k表示小科的编号，d表示小丁的编号。 第2到m+1行：每行两个空格分隔的整数x, y，表示x是y的双亲。 输出格式 一行：小科和小丁的最近公共祖先的编号，如果小科是小丁的祖先，则输出小科的编号，如果小丁是小科的祖先，那么输出小丁的编号。

这是一道树上最近公共祖先（LCA）的经典问题，可以使用倍增算法或Tarjan算法求解。

倍增算法的思路是，对于每个节点，预处理出它的 $2^i$ 级祖先（$i$ 为整数），然后对于每次询问，比较两个节点的深度，将深度较深的节点向上跳，一直跳到两个节点深度相同，然后同时向上跳，直到找到它们的最近公共祖先。

Tarjan算法的思路是，先进行一次深度优先遍历，记录每个节点的祖先和是否被访问过。然后对于每个查询，分别从两个节点出发，一直往上找，将找到的节点标记为访问过，如果发现某个节点已经被访问过，那么这个节点就是它们的最近公共祖先。

下面给出倍增算法的代码实现：

相关问题

C语言实现每行给出一对整数键值U和V，求找到最近公共祖先结点的键值A。

要实现这个功能，可以采用二叉树的数据结构，然后利用树的性质，通过递归遍历的方式来查找最近公共祖先。

具体的实现步骤如下：

1. 定义一个二叉树的结构体，包含键值和左右子节点指针。

2. 采用递归的方式遍历二叉树，查找节点U和V的位置。

3. 如果当前节点为NULL或者等于U或V，则返回当前节点。

4. 递归遍历左右子树，如果左右子树均返回非空节点，则当前节点为最近公共祖先。

5. 如果左右子树中只有一个返回非空节点，则继续向上递归。

6. 最终返回最近公共祖先节点的键值即可。

下面是实现代码的示例：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
} Node;

Node* create_node(int key) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Node* find_lca(Node* root, int u, int v) {
    if (root == NULL || root->key == u || root->key == v) {
        return root;
    }
    Node* left = find_lca(root->left, u, v);
    Node* right = find_lca(root->right, u, v);
    if (left != NULL && right != NULL) {
        return root;
    }
    return left != NULL ? left : right;
}

int main() {
    Node* root = create_node(1);
    root->left = create_node(2);
    root->right = create_node(3);
    root->left->left = create_node(4);
    root->left->right = create_node(5);
    root->right->left = create_node(6);
    root->right->right = create_node(7);

    int u = 4, v = 5;
    Node* lca = find_lca(root, u, v);
    printf("LCA of %d and %d is %d\n", u, v, lca->key);

    u = 4, v = 6;
    lca = find_lca(root, u, v);
    printf("LCA of %d and %d is %d\n", u, v, lca->key);

    u = 3, v = 7;
    lca = find_lca(root, u, v);
    printf("LCA of %d and %d is %d\n", u, v, lca->key);

    return 0;
}

输出结果如下：

LCA of 4 and 5 is 2
LCA of 4 and 6 is 1
LCA of 3 and 7 is 3

现代的人对于本家族血统越来越感兴趣。 题目描述 给出充足的父子关系,请你编写程c++

序，实现以下功能：

1. 查询某个人的祖先（父亲、爷爷、曾祖父等）；

2. 查询某个人的后代（儿子、孙子、曾孙等）；

3. 查询某个人的兄弟姐妹；

4. 查询某个人的堂兄弟堂姐妹；

5. 查询某个人的表兄弟表姐妹。

输入格式：

第一行包含两个整数 n 和 m，表示家族成员数量和查询次数。

接下来 n 行，每行包含一个字符串和一个整数，表示家族成员的姓名和父亲的编号。其中父亲的编号为 -1 表示该成员是家族的根节点。

接下来 m 行，每行包含一个查询操作和一个人的姓名。查询操作包括 ANCESTORS（查询祖先）、DESCENDANTS（查询后代）、SIBLINGS（查询兄弟姐妹）、COUSINS（查询堂兄弟堂姐妹）和 SECOND_COUSINS（查询表兄弟表姐妹）。

输出格式：

对于每次查询，输出查询结果，每个结果占一行，形式为“姓名1 姓名2 ...”，表示查询到的人的姓名列表，按照字典序从小到大排序。如果查询结果为空，则输出 -。

数据范围：

1 ≤ n,m ≤ 1000
1 ≤ 姓名长度 ≤ 10

输入样例：

10 6
A 1
B 2
C 2
D 3
E 3
F 4
G 4
H 5
I 5
J -1
ANCESTORS B
DESCENDANTS 3
SIBLINGS E
COUSINS B
SECOND_COUSINS A

输出样例：

A J
D E F G
C E
A D E F G
C H I