工作沟通
时间限制：2.0 s
内存限制：128.0 MB
问题描述
某公司有N名员工，编号从0至N-1。其中，除了0号员工是老板，其余每名员工都有一个直接领导。我们假设编号为i的员工的直接领导是fi。
该公司有严格的管理制度，每位员工只能受到本人或本人直接领导或间接领导的管理。具体来说，规定员工x可以管理员工y，当且仅当x=y，或f=fy，或x可以管理fy。特别地，0号员工老板只能自我管理，无法由其他任何员工管理。
现在，有一些同事要开展合作，他们希望找到一位同事来主持这场合作，这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工，他们希望找到编号最大的员工。你能帮帮他们吗？
输入描述
第一行一个整数N，表示员工的数量。
第二行N-1个用空格隔开的正整数，依次为f1,f2…,fN-1。
第三行一个整数Q，表示共有Q场合作需要安排。
接下来Q行，每行描述一场合作：开头是一个整数m（2≤m≤N），表示参与本次合作的员工数量；接着是m个整数，依次表示参与本次合作的员工编号（保证编号合法且不重复）。
保证公司结构合法，即不存在任意一名员工，其本人是自己的直接或间接领导。
输出描述
输出Q行，每行一个整数，依次为每场合作的主持人选。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
5 0 0 2 2 3 2 3 4 3 2 3 4 2 1 4
样例输出 1
2 2 0
样例解释 1
对于第一场合作，员工3,4有共同领导2，可以主持合作。
对于第二场合作，员工2本人即可以管理所有参与者。
对于第三场合作，只有0号老板才能管理所有员工。
样例输入 2
7 0 1 0 2 1 2 5 2 4 6 2 4 5 3 4 5 6 4 2 4 5 6 2 3 4
样例输出 2
2 1 1 1 0
数据规模
对于50%的测试点，保证N≤50。
对于所有测试点，保证3≤N≤300；Q≤100 。
相似题推荐
给定一棵二叉树，采用广度优先搜索(BFS) 算法，返回右视图所有节点的值。其中右视图定义为：二叉树的右视图是从树的右侧看过去时可见的节点集合，即右视图中的每个节点都是某一层中最右侧的节点。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def rightSideView(root):
rightmost_value_at_depth = {}
max_depth = -1
node_queue = []
depth_queue = []
node_queue.append(root)
depth_queue.append(0)
while node_queue:
node = node_queue.pop(0)
depth = depth_queue.pop(0)
if node is not None:
max_depth = max(max_depth, depth)
rightmost_value_at_depth[depth] = node.val
node_queue.append(node.left)
node_queue.append(node.right)
# (1) 填空处
depth_queue.append(depth + 1)
depth_queue.append(depth + 1)
right_view = []
# (2) 填空处
for depth in range(max_depth + 1):
right_view.append(rightmost_value_at_depth[depth])
return right_view
if __name__ == "__main__":
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
root.right.right = TreeNode(4)
print(rightSideView(root))| A． （1）depth , depth ;（2）0 , max_depth |
B． （1）depth + 1 , depth + 1 ;（2）0 , max_depth + 1 |
| C． （1）depth + 1 , depth + 1 ;（2）1 , max_depth + 1 |
D． （1）depth , depth ;（2）1 , max_depth |
游乐园的过山车每次限坐4 人，用循环队列管理排队（容量MAX=5，空一格判满）。下面代码执行后，循环队列是否已满？rear 的值是多少？
MAX = 5
queue = [None] * MAX
front = 0
rear = 0
def enqueue(x):
global rear, queue
queue[rear] = x
rear = (rear + 1) % MAX
def dequeue():
global front
front = (front + 1) % MAX
if __name__ == "__main__":
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)
dequeue()
dequeue()
enqueue(5)
enqueue(6)
print("队列数组: ", queue)
print("front下标位置: ", front)
print("rear下标位置: ", rear)| A． 已满，rear = 1 |
B． 未满，rear = 1 |
| C． 已满，rear = 2 |
D． 未满，rear = 4 |
设二叉树共有n个结点，函数 preorderTraversal 的时间复杂度为O(n)，空间复杂度为O(n)。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def preorder(root, res):
if root is None:
return
res.append(root.val)
preorder(root.left, res)
preorder(root.right, res)
def preorderTraversal(root):
res = []
preorder(root, res)
return res
if __name__ == "__main__":
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
result = preorderTraversal(root)
print("前序遍历结果: ", result) | A．正确 | B．错误 |
在二叉搜索树（BST）中，若中序遍历的序列为{1, 2, 3, 4, 5}，且先序遍历的第一个序列元素为3，则下列说法正确的是（）。
| A． 该树一定是一棵完全二叉树。 |
B． 元素4和5不可能是兄弟节点。 |
| C． 元素1所在节点的深度可能大于3（根节点深度为1）。 |
D． 元素2一定是元素1的父节点。 |
