#D1051. 树上 K 级祖先(弱化版)
树上 K 级祖先(弱化版)
题目描述
给定一棵 个点的有根树,直接给出每个点的父节点,根的父节点为 。
有 次询问,每次给出 和 ,求从 沿父边向上走 步到达的节点,也就是 的 级祖先。
输入格式
第一行两个整数 、。
第二行 个整数 ,其中 是点 的父节点。根的父节点为 。
接下来 行,每行两个整数 、,表示一次询问。
输出格式
输出 行,每行一个整数,表示对应询问的答案。
样例
7 5
0 1 1 2 2 3 3
4 1
4 2
6 2
7 1
5 0
2
1
1
3
5
5 3
0 1 2 3 4
5 1
5 4
3 0
4
1
3
样例解释
这棵树的根是 ,结构为:
1
├─ 2
│ ├─ 4
│ └─ 5
└─ 3
├─ 6
└─ 7
- 向上走 步到 ;
- 向上走 步到 ;
- 向上走 步到 ;
- 向上走 步到 ;
- 向上走 步还是 。
数据范围与约定
| 子任务 | 分值 | 限制 |
|---|---|---|
| , 的深度 |
保证输入是一棵有根树,根的父节点为 ,且每次询问向上走 步不会越过根。