#DS0705. LCA1

LCA1

题目描述

给你一棵树,树以下列方式给出:

树以下列方式给出:

  • 编号为 1 的节点为根;
  • 输入第一行给出一个数 nn,表示一共有 nn 个节点;
  • 接下来 n1n−1 行,每行给出两个数 x,y(xy)x,y(x≠y),表示 x,yx,y 之间有一条边。

接下来有 mm 组询问,每组询问有两个数 x,y(xy)x,y(x≠y), 你需要求出 x,yx,y 的最近公共祖先。

输入格式

见题面。

输出格式

输出共 mm 行,每行 1 个数表示每次询问答案。

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

数据规模

对于所有数据,保证 1n,m1000,1x,yn,xy1≤n,m≤1000,1≤x,y≤n,x≠y