수업 목표

학습 동기부여

도입 스토리

1. 트리 탐색과 서브트리 크기

# 8053번: 트리 탐색과 서브트리 크기 — 재귀 없는 O(N) 서브트리 크기 계산
import sys
input = sys.stdin.readline

n = int(input())
if n > 1:
    parent = [0] + list(map(int, input().split()))
else:
    parent = []

size = [0] * (n + 1)
# 노드 번호의 역순으로 순회하며 부모에게 크기를 전달
for i in range(n, 1, -1):
    p = parent[i - 2]
    size[p] += size[i] + 1

print(*(size[1:]))

2. 트리의 지름 (Tree Diameter)

# 8054번: 트리의 지름 — 투 패스 BFS 구현
import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
if n <= 1:
    print(0)
    sys.exit()

adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

def bfs(start):
    dist = [-1] * (n + 1)
    dist[start] = 0
    q = deque([start])
    
    max_d = 0
    far_node = start
    while q:
        curr = q.popleft()
        d = dist[curr]
        if d > max_d:
            max_d = d
            far_node = curr
        for nxt in adj[curr]:
            if dist[nxt] == -1:
                dist[nxt] = d + 1
                q.append(nxt)
    return far_node, max_d

u, _ = bfs(1)
v, diameter = bfs(u)
print(diameter)

3. 최소 공통 조상 (LCA, Lowest Common Ancestor)

# 8055번: 최소 공통 조상 — 이진 도약을 통한 O(log N) LCA 탐색
import sys
sys.setrecursionlimit(300000)
input = sys.stdin.readline

n, q = map(int, input().split())
parent = [0, 1]
if n > 1:
    parent += list(map(int, input().split()))

# Depth 계산 (parent[i] < i 성질 활용)
depth = [0] * (n + 1)
for i in range(2, n + 1):
    depth[i] = depth[parent[i]] + 1

LOG = 18
up = [[0] * (n + 1) for _ in range(LOG + 1)]
for i in range(1, n + 1):
    up[0][i] = parent[i]

for k in range(1, LOG + 1):
    for i in range(1, n + 1):
        up[k][i] = up[k - 1][up[k - 1][i]]

def get_lca(a, b):
    if depth[a] < depth[b]:
        a, b = b, a
    
    # 높이 맞추기
    diff = depth[a] - depth[b]
    for k in range(LOG, -1, -1):
        if (diff >> k) & 1:
            a = up[k][a]
            
    if a == b:
        return 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]

for _ in range(q):
    u, v = map(int, input().split())
    print(get_lca(u, v))

4. Heavy-Light 분해와 오일러 경로 테크닉

# 8056번: 트리 경로 가중치 쿼리 — 오일러 경로 테크닉과 펜윅 트리
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
v = [0] + list(map(int, input().split()))

adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

# 반복문 기반 DFS로 트리 계층 구조 및 Euler Tour 계산 (재귀 회피)
children = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
visited[1] = True
bfs_queue = [1]
head = 0
while head < len(bfs_queue):
    curr = bfs_queue[head]
    head += 1
    for nxt in adj[curr]:
        if not visited[nxt]:
            visited[nxt] = True
            children[curr].append(nxt)
            bfs_queue.append(nxt)

# DFS 방문 타임스탬프 기록
tin = [0] * (n + 1)
tout = [0] * (n + 1)
timer = 0
stack = [[1, 0]]
while stack:
    u, c_idx = stack[-1]
    if c_idx == 0:
        timer += 1
        tin[u] = timer
    
    if c_idx < len(children[u]):
        stack[-1][1] += 1
        stack.append([children[u][c_idx], 0])
    else:
        tout[u] = timer
        stack.pop()

# 펜윅 트리 구현 (구간 업데이트, 점 쿼리)
bit = [0] * (n + 2)

def bit_add(i, val):
    while i <= n:
        bit[i] += val
        i += i & (-i)

def bit_query(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & (-i)
    return s

def range_add(l, r, val):
    bit_add(l, val)
    bit_add(r + 1, -val)

# 초기 노드 가중치 적용
for i in range(1, n + 1):
    range_add(tin[i], tout[i], v[i])

# 쿼리 응답
for _ in range(q):
    line = list(map(int, input().split()))
    if line[0] == 1:
        s, x = line[1], line[2]
        diff = x - v[s]
        v[s] = x
        range_add(tin[s], tout[s], diff)
    else:
        u = line[1]
        print(bit_query(tin[u]))