#g6016. [GESP6级模拟题]家族关系

[GESP6级模拟题]家族关系

题目背景

小明最近在研究自己的家族族谱。族谱可以看作一棵树:始祖是树根,每一代人的子女连接到父辈之下。每个人的编号从 11nn,始祖编号为 11

小明想知道,对于族谱中的任意两个人,他们之间是祖先关系还是后辈关系,并算出隔了多少代。

题目描述

给定一棵 nn 个节点的树(11 为根),以及 mm 次询问。

每次询问给出两个编号 u,vu, v,请判断:

  • 如果 uuvv 的祖先,输出 ancestor X,其中 XX 为相差的代数(X>0X > 0
  • 如果 vvuu 的祖先,输出 descendant X
  • 如果两人没有直接血缘关系(即既不是祖先也不是后代),输出 unrelated

输入格式

第一行两个整数 n,mn, m

接下来 n1n-1 行,每行两个整数 p,cp, c,表示 ppcc 的父辈。

接下来 mm 行,每行两个整数 u,vu, v,表示一次询问。

输出格式

输出 mm 行,每行对应一次询问的结果。

样例输入

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
  • 询问 44554455 都是 22 的孩子,不是祖先关系 → unrelated
  • 询问 44111144 的祖先,相差 22 代 → descendant 2
  • 询问 11441144 的祖先,相差 22 代 → ancestor 2
  • 询问 5566:分属 2233 两支,无直接血缘 → unrelated

数据范围

1n10001 \le n \le 10001m1001 \le m \le 100