← 返回题单

题单练习树及树的应用

← 上一题下一题 →

A70774 | $树的公共祖先(LCA)(2)$

来源编程题

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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

输入格式

第 1 行输入一个整数 n ，代表结点数量（ n\leq100 ）； 第 2 行输入两个整数 x ， y ，表示需要计算的结点； 以下 n-1 行，每行两个整数 a 和 b ， 结点 a 和 b 是父子关系，但不保证 a 是 b 的父 ；

输出格式

x 与 y 的最近公共祖先。

输入输出样例

输入 #1

输出 #1

C++ 编辑器

输入

输出