题目 30004

最近公共祖先

查看题解 ↗GitHub ↗如何评测
题号
30004
时间限制
10000 ms
内存限制
1024 MB
标签
图论树LCA
来源
Library Checker (yosupo06) - lca

【题目描述】

给定一棵有 NN 个顶点的有根树。根为顶点 00,顶点 ii 的父亲为 pip_i。请处理 QQ 个查询,查询形式如下:

  • $u$ $v$:输出顶点 uu 与 vv 的最近公共祖先(LCA)。

【输入】

文本
$N$ $Q$
$p_1$ $p_2$ ... $p_{N-1}$
$u_0$ $v_0$
$u_1$ $v_1$
:
$u_{Q - 1}$ $v_{Q - 1}$

【输出】

对每个查询输出一行,表示对应两个顶点的最近公共祖先的编号。

【输入样例】

文本
5 5
0 0 2 2
0 1
0 4
1 2
2 3
3 4

【输出样例】

文本
0
0
0
2
2

【数据范围】

  • 2≤N≤5000002 \leq N \leq 500000
  • 1≤Q≤5000001 \leq Q \leq 500000
  • 0≤pi<i0 \leq p_i < i
  • 0≤u<v≤N−10 \leq u < v \leq N - 1

【来源】

Library Checker(yosupo06) lca

数据下载

题目 30004 的公开数据

正在读取文件列表…

常用命令

题目 30004 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。