수업 목표 및 핵심 역량

- 트리의 계층 구조와 간선 연결성을 정량적으로 분석합니다. - 재귀 호출의 깊이 한계를 인지하고 반복문 구조로 탐색을 대체하는 요령을 기릅니다. - 2의 거듭제곱 단위 조상 테이블 up[k][i]의 동적 계획법 구성을 내재화합니다. - 트리를 선형 배열의 연속된 서브트리 구간으로 매핑하는 원리를 습득합니다.

트리 탐색과 서브트리 크기

- 부모 노드가 자식보다 작을 때, 역순 순회로 $O(N)$에 서브트리 크기 계산

# 8053번: 트리 탐색과 서브트리 크기 발췌
size = [0] * (n + 1)
for i in range(n, 1, -1):
    p = parent[i - 2]
    size[p] += size[i] + 1

트리의 지름 (Tree Diameter)

- 두 번의 BFS 탐색으로 가장 먼 두 노드 사이의 거리 결정

# 8054번: 트리의 지름 발췌
u, _ = bfs(1)          # 임의의 시작점에서 가장 먼 노드 u 찾기
v, diameter = bfs(u)   # u에서 가장 먼 노드 v 찾고 거리 측정

최소 공통 조상 (LCA) 이진 도약

- 이진 도약을 통한 깊이 동기화 및 부모 추적

# 8055번: 최소 공통 조상 발췌
# up[k][i] = up[k-1][up[k-1][i]] (2^k번째 조상)
for k in range(LOG, -1, -1):
    if (diff >> k) & 1:
        a = up[k][a]
for k in range(LOG, -1, -1):
    if up[k][a] != up[k][b]:
        a = up[k][a]
        b = up[k][b]
return up[0][a]

오일러 투어 테크닉 (Euler Tour Technique)

- 트리를 구간으로 펴서 펜윅 트리를 통해 경로 가중치 갱신

# 8056번: 트리 경로 가중치 쿼리 발췌
# s의 서브트리 [tin[s], tout[s]] 가중치 갱신
range_add(tin[s], tout[s], diff)
# u의 경로 가중치 합 점 쿼리
path_sum = bit_query(tin[u])

오류 예방 및 안정성 체크

- **재귀 제한 해제**: 파이썬 깊이 한도를 sys.setrecursionlimit(300000) 등으로 확장하여 일자 트리 탐색 시 런타임 에러 방지 - **도약 조상 배열 예외**: 1번 루트 노드의 상위 조상을 참조할 때 0 또는 1로 고정하여 배열 인덱스 초과 차단 - **선형화 경계 설정**: 펜윅 트리 구간 업데이트 시 tout[s] + 1 값이 $N+1$ 배열 범위를 초과하지 않도록 크기 제어 보장