← 返回题目列表

Codeforces · 246/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,x > 0)。

如果编号为 b 的男子是编号为 a 的男子的 k 祖先,则我们将编号为 a 的男子称为编号为 b 的男子的 k 儿子。

Polycarpus 对每个人有多少个儿子以及哪些儿子非常感兴趣。他拿了一张纸,写下了m对数字vi,ki。帮助他了解每一对 vi、ki 中编号为 vi 的人的 ki-sons 的所有名字中不同名字的数量。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 105) — 树中的人数。接下来的 n 行包含树中人员的描述。第 i 行包含空格分隔的字符串 si 和整数 ri (0 ≤ ri ≤ n),其中 si 是编号为 i 的人的姓名,ri 是编号为 i 的人的直系祖先的编号,如果编号为 i 的人没有直系祖先,则 ri 是 0。

下一行包含一个整数 m (1 ≤ m ≤ 105) — Polycarpus 的记录数。接下来的 m 行包含空格分隔的整数对。第 i 行包含整数 vi、ki (1 ≤ vi, ki ≤ n)。

保证家庭关系不形成循环。所有人的名字都是非空字符串,由不超过20个小写英文字母组成。

输出

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

示例

输入 #1

6
pasha 0
gerald 1
gerald 1
valera 2
igor 3
olesya 1
5
1 1
1 2
1 3
3 1
6 1

输出 #1

2
2
0
1
0

输入 #2

6
valera 0
valera 1
valera 1
gerald 0
valera 4
kolya 4
7
1 1
1 2
2 1
2 2
4 1
5 1
6 1

输出 #2

1
0
0
0
2
0
0