← 返回题单
题单练习 树及树的应用
← 上一题 下一题 →

A70775 | 树的公共祖先(LCA)(3)

来源编程题
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一棵 n 个结点的树（结点标号 1 \dots n ）以及树中结点的边，结点 s 为树的根。

有 m 次询问，请求出每次询问的两个结点 x 和 y 的最近的公共祖先结点。

输入格式

第 1 行输入 3 个整数 n、m、s（n≤500000，m≤500000，1≤s≤n）；

接下来 n-1 行，每行两个整数 a 和 b ，结点 a 和 b 是父子关系，但不保证 a 是 b 的父，数据保证一定能构成树；

接下来 m 行，每行两个整数 x，y，表示要求出 x 和 y 结点的公共祖先。

输出格式

输出 m 行，每行一个整数，表示 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
C++ 编辑器
输入
输出