填空题
牛牛的家谱
发布于 2022-03-03 16:36:47
一天牛牛整理旧物时发现了一张家谱（家谱可以看做一棵树）。由于年代久远，家谱已经模糊了，现在只能看见人与人之间有直接关系，但是看不出来直接关系是什么了（就是说现在还能直接看出u与v之间有父子关系，但是看不出来是u是v的父亲还是v是u的父亲了）。牛牛还不知道他们家族的最大祖先（根节点）是谁，这样显然就不知道家谱中任意两个人是什么关系了，但是牛牛的爷爷告诉了牛牛家每个人都有多少个孩子（显然叶子节点的孩子数为0），这样就可以推出人与人之间的关系了。家谱中一共有n个人，编号为1~n。牛牛现在有q次询问，对于每个询问，有两个数u和v。对于每组询问输出一行表示他们之间关系。
输入描述：
第一行一个正整数n分别表示家谱中人数
接下来n-1行每行两个正整数w，r，表示w，r是父子关系（但不知道谁是谁的父亲）（即w，r在家谱上有一条边相连）。
接下来一行有n个整数，第i个数代表标号为i的人的孩子的个数
接下来一行一个正整数q表示询问次数
接下来q行，每行两个正整数u，v
输入样例： 4 3 4 1 2 3 1 2 0 1 0 3 1 2 4 1 2 4 输出描述： 对于每组询问
如果u是v的祖先，输出“ZZZZ”；（引号不输出）
如果v是u的祖先，输出“SSSS”；（引号不输出）
如果u，v互相都不是另一个人的祖先，则输出他们的最近公共祖先的编号
每组询问输出一行
输出样例 ZZZZ SSSS 1
接下来n-1行每行两个正整数w，r，表示w，r是父子关系（但不知道谁是谁的父亲）（即w，r在家谱上有一条边相连）。
接下来一行有n个整数，第i个数代表标号为i的人的孩子的个数
接下来一行一个正整数q表示询问次数
接下来q行，每行两个正整数u，v
输入样例： 4 3 4 1 2 3 1 2 0 1 0 3 1 2 4 1 2 4 输出描述： 对于每组询问
如果u是v的祖先，输出“ZZZZ”；（引号不输出）
如果v是u的祖先，输出“SSSS”；（引号不输出）
如果u，v互相都不是另一个人的祖先，则输出他们的最近公共祖先的编号
每组询问输出一行
输出样例 ZZZZ SSSS 1
关注者
0
被浏览
11
