from collections import deque
node = int(input())
node_list =[]
node_idx_list =[]
child_node_list =[]
for tmp_node in range(node):
num_list = list(map(int,input().split()))
node_list.append(num_list)
node_idx_list.append(num_list[0]) # 루트부터 들어오지 않는 경우도 있어서 node idx list를 만들어서 보관해야함
if num_list[1] !=-1: # -1이 아니면 자식노드 리스트에 추가
child_node_list.append(num_list[1])
if num_list[2] != -1:
child_node_list.append(num_list[2])
for i in node_idx_list:
if i not in child_node_list:
root_node = i #자식 노드 리스트에 없는 노드가 루트 노드임
idx = 0
level_left=[0]*node # 레벨에서 가장 왼쪽에 있는 노드
level_right=[0]*node # 레벨에서 가장 오른쪽에 있는 노드
que =deque() # 노드 리스트를 보관하는 큐
result_que = deque() # 문제에서 주어진 트리의 순서대로 노드를 배치하는 큐
root_node_idx = node_idx_list.index(root_node) #찾은 root의 idx를 통해서 처음 시작 root node를 정해준다.
result_que.append(node_list[root_node_idx][0])
level = 1
idx = 0
tmp_que = deque() #레벨을 부여해주기 위해 임시로 사용하는 큐
tmp_que.append([0,node_list[root_node_idx]])
que.append([0,node_list[root_node_idx]])
while len(tmp_que)>0:
tmp_node = tmp_que.popleft()
tmp_level = tmp_node[0]
left_node = tmp_node[1][1]
right_node = tmp_node[1][2]
if left_node != -1: #레벨을 부여해주는 작업을 수행하고, que에 넣는다.
left_node_idx = node_idx_list.index(left_node)
tmp_que.append([tmp_level+1,node_list[left_node_idx]])
que.append([tmp_level+1,node_list[left_node_idx]])
if right_node != -1:
right_node_idx = node_idx_list.index(right_node)
tmp_que.append([tmp_level+1,node_list[right_node_idx]])
que.append([tmp_level+1,node_list[right_node_idx]])
same_level_node =[] #level 마다 존재하는 노드들을 구분하기 위한 리스트
same_level = 0
for i in range(len(que)):
now = que[i]
level = now[0]
now_node = now[1][0]
if same_level != level:
if len(same_level_node)> 0:
level_left[level-1] = same_level_node[0]
level_right[level-1] = same_level_node[-1]
same_level_node =[]
same_level = level
same_level_node.append(now_node)
#동일한 레벨에서 가장 왼쪽 값과 가장 오른쪽 값이 어딘지 확인하고 level_left or right에 넣어준다.
level_left[level] = same_level_node[0]
level_right[level] = same_level_node[-1]
while len(que)>0: #문제에서 주어진 트리대로 배치하는 방법
tmp = que.popleft()
tmp_level = tmp[0]
tmp_node = tmp[1][0]
left_node = tmp[1][1]
right_node = tmp[1][2]
result_tmp_idx = result_que.index(tmp_node)
if left_node != -1:
if result_tmp_idx ==0:
result_que.appendleft(left_node)
else:
result_que.insert(result_tmp_idx,left_node)
result_tmp_idx +=1
if right_node != -1:
result_que.insert(result_tmp_idx+1,right_node)
level_length =[0]*node
for i in range(len(level_left)): #각각의 레벨별로 왼쪽값의 index와 오른쪽 값의 index를 구하고 차이값을 level_length에 저장한다.
if level_left[i] !=0:
left_idx = result_que.index(level_left[i])
right_idx = result_que.index(level_right[i])
level_length[i] = right_idx-left_idx+1
maxist = 0
max_idx = 0
for i in range(len(level_length)): #가장 높은 값을 찾아주고, 동일할 경우에는 패스하도록 설정
if level_length[i] > maxist:
maxist = level_length[i]
max_idx = i
print(str(max_idx+1)+" "+str(maxist))
예시에는 root node가 1번부터 시작하고 맨 위에 존재하지만, 문제 case에는 root node부터 시작하지 않을 수도, node의 순서대로 들어오지 않을 수 있다.
level을 2**level - 1 방식으로 해보려고 했는데 완전 이진트리가 아니기 때문에 이 방식으로 레벨을 부여해서는 안된다.
큐를 이용해서 레벨을 부여, 다만 완전한 node 순서를 보유하고있는 que도 필요하므로 tmp_que를 선언해서 node마다 레벨을 부여했다.
부여된 레벨을 이용해서 레벨별 왼쪽 끝 노드와 오른쪽 끝 노드를 구한다.
루트노드에서 좌우 Child node를 정해주기때문에, 입력데이터가 아무렇게나 들어와도 que에는 노드 순서대로 들어가 있다.
따라서 동레벨의 가장 왼쪽 값과 오른쪽값만 구하면 된다.
문제에서 주어진 트리대로 배치하고 idx만 찾아서 계산해주면 된다.