题目描述

给定一棵树和两个不同的结点，求出他们最近的公共祖先父结点。已知该树有 $n$ 个结点，标号 $1 \sim n$ 。

输入格式

第 1 行输入一个整数 $n$ ，代表结点数量（$n \le 100$）

第 2 行输入两个整数 $x,y$，表示需要计算的结点

以下 $n-1$ 行，每行两个整数 $a$ 和 $b$，表示 $a$ 的父结点是 $b$ 。

输出格式

$x$ 与 $y$ 的最近公共祖先 $lca$ 。

样例

9
9 7
2 1
3 2
4 2
5 3
8 5
9 5
6 4
7 4

2

题目分析

首先本题的数据量很少，所以即便是很笨的方法，也能通过。为了学习倍增法求 LCA ，有必要先学习一下暴力枚举的方法。暴力枚举的方法比较容易理解，只不过效率比较低。

树上的任何一点 $u$ 到 跟 $root$ 的路径都是唯一的，而这条路径其实是一条链(数据结构的概念，如果没有这方面的知识，请先进行补充)。以下图为例：

节点 M 到根的链是 M -> H -> D -> A

节点 F 到根的链是 F -> B -> A

很容易知道，这些链都有共同的终点：根，但是出发点各不相同。而求 $u$ ，$v$ 两点的最近公共祖先其实就是求出两条链的第一个相同元素，从这个元素开始，后面的元素都一定相同。

所以，M 点 和 F 点的 LCA 是 A。

J 点到根的链是 J -> D -> A

所以，M 点和 J 点的 LCA 是 D 。

所以，求 $u$ ，$v$ 的 LCA 的一个朴素方法是从 $u$ 和 $v$ 出发，一个个比较，找出第一个相同的元素。这就需要到链的遍历法则。

暴力搜索 lca 分两种情况：

1. 已经通过 dfs 算法完成了建树，每一个节点的父亲已经知道，每一个节点的深度也已经知道：

   • 比较的时候，有一个很重要的基本信息：如果两个点的深度不一样，那这两个点肯定不是同一个点，根本就不用比较，我们这时候只需要从深度更大的那个点跳转到它的父亲。
   • 而如果两点的深度是一样的前提下，假设这两个点相同，则意味着找到 LCA 了，不用比较下去；如果两个点不相同，则比较它们的父亲，所以，这是一个递归的比较过程。
   • 这个递归的过程不需要担心出现死循环，因为最坏的情况下，$u$ ，$v$ 有公共祖先 $root$，比较到 $root$ 的时候，一定就是相同，不会无限往深处递归。

2. 树的结构并没厘清，不知道每个节点的深度，只知道每个节点的父亲（本题属于这种情况）

   • 可以开辟一个脚印数组，先从 $u$ 点出发，一直到根，沿途打上标记
   • 从 $v$ 出发到往根的方向走，当找到任何一个有印记的节点，则是 lca

程序填空

#include<bits/stdc++.h>
using namespace std;
int n,fa[101],f[101];

int get_lca(int u, int v){
	__填空（1）__;
	while(fa[u]){
		u = __填空（2）__;
		f[u] = true;
	}

	while(__填空（3）__){
		v = fa[v];
	}
	return __填空（4）__;
}
int main()
{
	scanf("%d",&n);

	int x,y;
	scanf("%d%d",&x,&y);

	int u,v;
	for(int i=2;i<=n;i++){
		scanf("%d%d",&u,&v);
		fa[u] = v;
	}

	cout<<get_lca(x,y);

	return 0;
}

填空（1）:{{ input(1) }}

填空（2）:{{ input(2) }}

填空（3）:{{ input(3) }}

填空（4）:{{ input(4) }}