#O1055. 树上第 k 祖先
树上第 k 祖先
题目描述
给定一棵 个点的树,其中 号点为根,()号点的父亲为 ,保证 。回答 次询问,每次给出 ,求 的第 级祖先(向上走 条边);若不存在输出 0。 时输出 自己。
题目类型
树上倍增
输入格式
第一行两个整数 。
第二行 个整数 ( 时该行留空)。
接下来 行,每行两个整数 。
输出格式
共 行,每行一个整数。
样例 #1
样例输入 #1
5 2
1 2 2 4
5 2
3 5
样例输出 #1
2
0
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 点数与询问数 | |
| 上跳步数 |
- 倍增表
up[k][u],不存在时记为 0。