4025: 树上两点距离查询

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：10 解决：7

题目描述

给定一棵包含 n 个节点的树，根节点为 0。有 q 次查询，每次查询给出两个节点 u 和 v，求从 u 到 v 的最短路径上经过的边数（即距离）。

输入

第一行一个整数 n，表示节点数量。 第二行 n-1 个整数，第 i 个数表示节点 i 的父亲节点（1 ≤ i ≤ n-1）。 第三行一个整数 q，表示查询次数。 接下来 q 行，每行两个整数 u 和 v。

输出

输出 q 行，每行一个整数，表示 u 到 v 的距离。

样例输入 复制 

5
0 0 2 2
3
3 4
1 4
2 3

样例输出 复制 

2
3
1

来源/分类

提交提交记录统计露一手!