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

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

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

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

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