CF246E Blood Cousins Return

Polycarpus 得到了一棵家族树。该树描述了 $n$ 个人（编号从 $1$ 到 $n$）之间的家庭关系。树中的每个人至多只有一位直接祖先，并且每个人都有一个名字，名字不一定唯一。 若编号为 $a$ 的人是编号为 $b$ 的人的直接祖先，则称 $a$ 是 $b$ 的 $1$ 级祖先。 对于 $k>1$，若编号为 $b$ 的人有 $1$ 级祖先，且编号为 $a$ 的人是该 $1$ 级祖先的 $(k-1)$ 级祖先，则称 $a$ 是 $b$ 的 $k$ 级祖先。 树中的家庭关系不构成环。换句话说，不存在某个人是自己的直接或间接祖先（即不存在某个 $x>0$，使得某人是自己的 $x$ 级祖先）。 若编号为 $b$ 的人是编号为 $a$ 的人的 $k$ 级祖先，则称 $a$ 是 $b$ 的 $k$ 级儿子。 Polycarpus 非常关心每个人有多少个儿子以及是哪些儿子。他在纸上写下了 $m$ 个数对 $v_i, k_i$。请你帮他，对于每一对 $v_i, k_i$，求出编号为 $v_i$ 的人的所有 $k_i$ 级儿子的名字中，不同名字的个数。

第一行包含一个整数 $n$ $ (1 \le n \le 10^{5}) $，表示家族树中的人数。接下来的 $n$ 行描述树中的人。第 $i$ 行包含字符串 $s_i$ 和整数 $r_i$ $ (0 \le r_i \le n) $，其中 $s_i$ 是编号为 $i$ 的人的名字，$r_i$ 是编号为 $i$ 的人的直接祖先的编号，如果没有直接祖先则为 $0$。 接下来一行包含一个整数 $m$ $ (1 \le m \le 10^{5}) $，表示 Polycarpus 的记录数。接下来的 $m$ 行每行包含两个整数 $v_i, k_i$ $ (1 \le v_i, k_i \le n) $。 保证家族关系没有环。所有人的名字是非空字符串，且不超过 $20$ 个小写英文字母。

输出 $m$ 个用空格分隔的整数，顺序对应输入的每条记录。每个整数表示 Polycarpus 所要求的不同名字的个数。

由 ChatGPT 5 翻译