题目描述

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

输入格式

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

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

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

输出格式

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

样例

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

2

算法分析

根据样例数据，画出的树如下图：

步骤 1：从 x (顶点 9) 开始，一路往上遍历，把 x 的所有祖先都打上标记。

步骤 2：从 y (顶点 7) 开始，一路往上遍历，如果遇到某个祖先是有标记的，就说明这个顶点既是 x 的祖先，也是 y 的祖先，而且，是最挨近 x 和 y 的共同祖先，它就是答案。

完善程序

#include<bits/stdc++.h>
using namespace std;
int n,fa[101],f[101];
int main()
{
	scanf("%d",&n);
	int x,y;
	scanf("%d%d",&x,&y);
	int a,b;
	for(int i=2;i<=n;i++)
	{
		scanf("%d%d",&a,&b);
		fa[填空(1)] = 填空(2); //记录父子关系 
	}

	while(填空(3))
	{
		f[x] = true;
		x = 填空(4);
	}
	
	while(填空(5))
		y=填空(6);
	
	cout<<y;

	return 0;
}

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

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

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

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

填空(5):{{ input(5) }}

填空(6):{{ input(6) }}