4358. 二叉树深度

【题目描述】

给定一棵有 $n$ 结点的二叉树，它的结点编号从 $1 \sim n$，现在需要询问它的某些子树的高度。

常规的树高度定义：从根到最远叶子结点的边数。

本题中树高度定义：从根到最远叶子结点数。

【输入格式】

第一行一个整数 $n$，表示树的大小。

接下来 $n$ 行，第 $i$ 行两个整数，分别表示结点 $i$ 的左右孩子，如果没有对应孩子，则数字为 $0$。

接下来一行一个整数 $q$，表示询问的次数。

接下来 $q$ 行，每行一个整数 $x$，表示询问以 $x$ 为根的子树的高度。

【输出格式】

共 $q$ 行，每行一个整数，表示对应子树的高度。

【样例输入】

9
6 4
5 7
9 2
0 0
0 8
0 0
0 0
0 0
1 0
3
9
5
4

【样例输出】

3
2
1

【数据规模与约定】

对于 $60\%$ 的数据,$1 \leq n \leq 2000$。

对于 $100\%$ 的数据，$1\leq n\leq 5 \times 10^4, 1 \leq q \leq n$。