https://acm.ecnu.edu.cn/contest/620/problem/J/

题目描述

给你一棵 $n$ 个节点的树和 $m$ 个问题，每个问题给出一对节点 $(u,v)$，请你回答它们在树上的最近公共祖先。

输入格式

第一行包含两个整数 $n,m$，表示树的节点数和问题数。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示树中存在一条从节点 $u$ 连向节点 $v$ 的边。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示一次询问。

输出格式

输出共 $m$ 行，每行一个整数，表示对应询问的答案。

数据范围

$1≤n, m≤10^5$

输入样例

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

输出样例

1
2
1

算法1

(LCA)

时间复杂度

$O(mlog(n))$

C++ 代码

算法2

(倍增)

时间复杂度

$O(mlog(n))$

C++ 代码