如何通过倍增法深入探讨求解最近公共祖先问题？

本文共计3575个文字，预计阅读时间需要15分钟。

题目描述：Luogu P3379 最近公共祖先问题实现，给定一棵有根多叉树，请求输出指定两个点的最近公共祖先。

输入格式：第一行包含三个正整数 \(N\)，\(M\)，\(S\)，分别表示树的节点数、询问数和根节点编号（从1开始计数）。

接下来的 \(M\) 行，每行包含两个正整数 \(u\)，\(v\)，表示一个询问，询问编号为 \(u\) 和 \(v\) 的两个点的最近公共祖先。

输出格式：对于每个询问，输出一行，包含一个整数，表示两个点的最近公共祖先的编号。如果不存在最近公共祖先，则输出 `-1`。

Luogu P3379 最近公共祖先 原题展现 题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 \(N,M,S\)，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 \(N-1\) 行每行包含两个正整数 \(x, y\)，表示 \(x\) 结点和 \(y\) 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 \(M\) 行每行包含两个正整数 \(a, b\)，表示询问 \(a\) 结点和 \(b\) 结点的最近公共祖先。

输出格式

输出包含 \(M\) 行，每行包含一个正整数，依次为每一个询问的结果。

样例输入 #1

5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5 样例输出 #1

4 4 1 4 4 提示

对于 \(30\%\) 的数据，\(N\leq 10\)，\(M\leq 10\)。

对于 \(70\%\) 的数据，\(N\leq 10000\)，\(M\leq 10000\)。