33OJ
登录 注册

#D1051. 树上 K 级祖先(弱化版)

树上 K 级祖先(弱化版)

题目描述

给定一棵 nn 个点的有根树,直接给出每个点的父节点,根的父节点为 00。

有 qq 次询问,每次给出 xx 和 kk,求从 xx 沿父边向上走 kk 步到达的节点,也就是 xx 的 kk 级祖先。

输入格式

第一行两个整数 nn、qq。

第二行 nn 个整数 f1,f2,…,fnf_1,f_2,\dots,f_n,其中 fif_i 是点 ii 的父节点。根的父节点为 00。

接下来 qq 行,每行两个整数 xx、kk,表示一次询问。

输出格式

输出 qq 行,每行一个整数,表示对应询问的答案。

样例

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

样例解释

这棵树的根是 11,结构为:

1
├─ 2
│  ├─ 4
│  └─ 5
└─ 3
   ├─ 6
   └─ 7
  • 44 向上走 11 步到 22;
  • 44 向上走 22 步到 11;
  • 66 向上走 22 步到 11;
  • 77 向上走 11 步到 33;
  • 55 向上走 00 步还是 55。

数据范围与约定

子任务 分值 限制
11 100100 1≤n,q≤1051 \le n,q \le 10^5,0≤k≤x0 \le k \le x 的深度

保证输入是一棵有根树,根的父节点为 00,且每次询问向上走 kk 步不会越过根。