5174. subtree, 5176 이진탐색, 5177. 이진 힙, 5178. 노드의 합

서브트리

T = int(input())
 
def search(N):
    global result
    result += 1
    for i in node_t[N]:
        search(i)
 
for tc in range(1,T+1):
    E, N = map(int,input().split())
    node = list(map(int,input().split())) # 부모 + 자식 노드 번호 상
    node_t = [[] for _ in range(E + 2)]
 
    idx = 1
    for i in node[::2]:
        node_t[i].append(node[idx])
        idx += 2
    result = 0
    search(N)
    print("#{} {}".format(tc, result))

 
def tree(t):
    global cnt
    if t<=N: #배열 크기 넘기지않기
        tree(t*2) #왼쪽 노드는 현재 인덱스의 2배로
        node_t[t]=cnt #더이상 못가면 값넣기
        cnt += 1 # 값넣었으면 증가시키기
        tree(t*2+1) # 우측 노드는 인덱스 2배 + 1
 
T = int(input())
 
for tc in range(1, T+1):
    N = int(input())
    node_t = [0 for i in range(N+1)]
    cnt = 1
    tree(1)
 
    print("#{} {} {}".format(tc, node_t[1], node_t[N//2]))

T = int(input())
 
for tc in range(1, T+1):
    N = int(input())
    Num = list(map(int, input().split()))
 
    tree = [0]* (N+1) # 초기화
    for i in range(N):
        tree[i+1] = Num[i]
        while i > 0:
            if tree[i+1] < tree[(i+1)//2]:
                tree[i+1], tree[(i+1)//2] = tree[(i+1)//2], tree[i+1]
                i=(i+1)//2 -1
            else:
                break
    result = 0
 
    j=N
    while j > 0:
        j //= 2
        result += tree[j]
    print("#{} {}".format(tc, result))
 
 
# def insertHeap(data):
#     pos= len(HEAP)
#     HEAP.append(data)
#     while pos > 1 and HEAP[pos] < HEAP[pos//2]:
#         HEAP[pos], HEAP[pos // 2] = HEAP[pos//2], HEAP[pos]
#         pos //= 2
#
# def sumAn():
#     pos = (len(HEAP)-1)//2
#     sumV = 0
#     while pos >= 1:
#         sumV += HEAP[pos]
#         pos//= 2
#         return sumV
#
# T = int(input())
# for tc in range(1, T+1):
#     N=int(input())
#     lst = list(map(int, input().split()))
#     HEAP = [0]
#

#아까했던 것과 거의 비슷하다.
#순회하는 순서만 바꿔주면된다.
#
def f(root):
    if root:
        lv = f(root의 왼쪽)
        rv = f(root의 오른쪽)
        TREE[root] = lv + rv
        return lv+rv
########################################
 
# D2 5178 노드의 합
def dfs(idx):
    # 만약 인덱스 범위를 벗어난다면 0을 리턴
    if idx > N + 1: return 0
    # 값이 있다면 값을 리턴
    if Tree[idx]: return Tree[idx]
    # 왼쪽 자식노드 위치찾기
    left = idx * 2
    # 오른쪽 자식노드 위치찾기
    right = left + 1
    # 재귀를 이용하여 구하기
    Tree[idx] = dfs(left) + dfs(right)
    # 결과값 리턴
    return Tree[idx]
 
 
for t in range(int(input())):
    # 별도 노드개수, 리프노드의 개수, 출력노드번호
    N, M, L = map(int, input().split())
    # 누적합을 적어둔 리스트
    Tree = [0 for _ in range(N + 2)]
    # 입력값을 받아 노드의 값을 수정한다.
    for i in range(M):
        node, value = map(int, input().split())
        Tree[node] = value
    # 재귀를 이용하여 계산시작
    result = dfs(L)
    # 결과값 출력
    print('#{} {}'.format(t + 1, result))
########################################
 
# T = int(input())
# for tc in range(1,T+1):
#