编程题
### 问题描述 您是一位家谱研究员,负责管理一个庞大的家庭树。家庭树由 $N$ 个成员和 $N - 1$ 条边组成,每条边表示一个父子关系。您需要处理 $Q$ 个查询,每个查询会问您两个家庭成员之间的关系是什么。您的任务是,根据这些查询快速地确定他们之间的关系。 关系定义 $Ancestor$(前辈): 如果一个成员在树中的深度小于另一个成员。 $Sibling$(同辈): 如果两个成员在树中有相同的深度。 $Descendant$(后辈): 如果一个成员在树中的深度大于另一个成员。 ### 输入格式 第一行包含一个整数 $N$ ,表示家庭成员的数量。 接下来的 $N - 1$ 行,每行包含两个整数 $u$ 和 $v$ ,其中成员 $u$ 是成员 $v$ 的父节点。 接下来的一行包含一个整数 $Q$ ,表示查询的数量。 接下来的 $Q$ 行,每行包含两个整数 $a$ 和 $b$ ,表示您需要确定成员 $a$ 和成员 $b$ 之间的关系。 ### 输出格式 对于每个查询,输出一行,表示成员 $a$ 相对于成员 $b$ 是 $Ancestor$ 、$Sibling$ 还是 $Descendant$ 。 ### 样例输入 ``` 8 1 2 2 3 3 4 4 5 1 6 2 7 3 8 3 5 8 2 7 1 6 ``` ### 样例输出 ``` Descendant Ancestor Ancestor ``` ### 评测数据范围 $2 \leq N, Q \leq 10^5$ 。
查看答案
赣ICP备20007335号-2