#g6016. [GESP6级模拟题]家族关系
[GESP6级模拟题]家族关系
题目背景
小明最近在研究自己的家族族谱。族谱可以看作一棵树:始祖是树根,每一代人的子女连接到父辈之下。每个人的编号从 到 ,始祖编号为 。
小明想知道,对于族谱中的任意两个人,他们之间是祖先关系还是后辈关系,并算出隔了多少代。
题目描述
给定一棵 个节点的树( 为根),以及 次询问。
每次询问给出两个编号 ,请判断:
- 如果 是 的祖先,输出
ancestor X,其中 为相差的代数() - 如果 是 的祖先,输出
descendant X - 如果两人没有直接血缘关系(即既不是祖先也不是后代),输出
unrelated
输入格式
第一行两个整数 。
接下来 行,每行两个整数 ,表示 是 的父辈。
接下来 行,每行两个整数 ,表示一次询问。
输出格式
输出 行,每行对应一次询问的结果。
样例输入
7 4
1 2
1 3
2 4
2 5
3 6
3 7
4 5
4 1
1 4
5 6
样例输出
unrelated
descendant 2
ancestor 2
unrelated
样例解释
族谱结构:
1
/ \
2 3
/ \ / \
4 5 6 7
- 询问 和 : 和 都是 的孩子,不是祖先关系 →
unrelated - 询问 和 : 是 的祖先,相差 代 →
descendant 2 - 询问 和 : 是 的祖先,相差 代 →
ancestor 2 - 询问 和 :分属 和 两支,无直接血缘 →
unrelated
数据范围
,。