‹ 上一题下一题 ›

j00589. 一般树的 LCA 未做

1000 ms 256 MB 测试点 10 7级·树上问题树的概念树的表示与存储二叉树的遍历深度优先搜索 7级·树上路径与LCA 阶梯·运用树上路径与LCA LCA与树上距离

文件读写输入j00589.in输出j00589.out

题目描述

小杨把家族成员的关系整理成一棵以 1 为根的树，并用父数组形式存了下来：每个结点都记着自己的父亲是谁。现在他想查一次：两位成员 $u, v$ 的最近公共祖先（LCA）是谁，也就是同时是两位成员祖先、且离根最近的那个结点？请输出这个结点的编号。

输入格式

第一行一个整数 $n$ ；第二行 $n - 1$ 个整数 $f_{2} .. f_{n}$ ；第三行两个整数 $u, v$ 。

输出格式

一行一个整数，LCA 的编号。

样例

输入

5
1 1 2 3
3 5

输出

数据范围

$1 \leq n \leq 1 0^{5}$
$1 \leq u, v \leq n$
$1 \leq f_{i} < i$ （ $2 \leq i \leq n$ ， $f_{i}$ 为 $i$ 的父亲）

输入

输出

答案