2198: 【提高】树的公共祖先(LCA)(3)

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:2 通过:1

题目描述

给定一棵n个结点的树(结点标号1..n)以及树中结点的边,结点s为树的根。

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

输入格式

第1行输入3个整数n、m、s(n≤500000,m≤500000,1s≤n) 

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

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


输出格式

输出m行,每行一个整数,表示m次询问求出的结果

输入样例 复制

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出样例 复制

4
4
1
4
4

分类标签