← 返回题目列表

Codeforces · 208/E

E. 血亲

中文机器翻译题面 查看原题

Polycarpus 掌握了家庭关系树。该树描述了 n 个人的家庭关系,编号为 1 到 n。树中的每个人都只有一个父母。

如果 a 是 b 的父代,我们称 a 为 b 的 1-祖先。

如果人 b 有一个 1-祖先,并且 a 是 b 的 1-祖先的 (k - 1)-祖先,我们称人 a 为人 b 的 k-祖先 (k > 1)。

家庭关系不会在找到的树中形成循环。换句话说,没有人直接或间接地是他自己的祖先(即,对于他自己来说,对于某些x,x > 0,他是x祖先)。

如果有一个人 z,他是 x 的 p 祖先和 y 的 p 祖先,我们称两个人 x 和 y (x ≠ y) 为 p 代表兄弟姐妹 (p > 0)。

Polycarpus 想知道每个人有多少个表亲以及它们的种类。他拿了一张纸,写下了m对整数vi,pi。帮助他计算出 vi 的每对 vi、pi 有 pi 个表兄弟姐妹的数量。

输入

第一个输入行包含一个整数 n (1 ≤ n ≤ 105) — 树中的人数。下一行包含 n 个空格分隔的整数 r1, r2, ..., rn,其中 ri (1 ≤ ri ≤ n) 是人 i 的父母的数量,如果人 i 没有父母,则为 0。保证家庭关系不会形成循环。

第三行包含一个数字 m (1 ≤ m ≤ 105) — Polycarus 的家庭关系查询数量。接下来的 m 行包含空格分隔的整数对。第 i 行包含数字 vi、pi (1 ≤ vi, pi ≤ n)。

输出

打印 m 个以空格分隔的整数 — Polycarpus 查询的答案。按查询在输入中出现的顺序打印查询的答案。

示例

输入 #1

6
0 1 1 0 4 4
7
1 1
1 2
2 1
2 2
4 1
5 1
6 1

输出 #1

0 0 1 0 0 1 1