Link/Cut Tree에서 경로 쿼리 처리: 합, 최댓값, 노드 갱신까지 완전 이해

이번 글에서는 **Link/Cut Tree(LCT)**에서
경로상의 합, 최댓값, 노드 값 변경 등의 쿼리 처리를 어떻게 구현하는지
세부적으로 설명합니다.

앞선 글에서 LCT의 구조와 기본 연산들을 익혔다면,
이제는 실전 문제에서 많이 등장하는 경로 쿼리(Path Query) 기능을
어떻게 Augmentation으로 구현하는지를 마스터할 차례입니다.

✅ 목표 연산 정리

연산 설명

path_sum(u, v)	u–v 경로의 값 합계
path_max(u, v)	u–v 경로의 최댓값
update_node(u, val)	노드 u의 값을 변경
update_path(u, v, val)	u–v 경로 값 일괄 변경 (Lazy Propagation 포함)

🔧 기본 LCT 구조 복습

class LCTNode:
    def __init__(self, value):
        self.value = value
        self.path_sum = value
        self.path_max = value
        self.left = None
        self.right = None
        self.parent = None
        self.rev = False
        self.lazy_add = 0  # for range add

🧠 Augmentation 핵심 로직

1. update(node): 자식 정보 갱신

def update(node):
    node.path_sum = node.value
    node.path_max = node.value
    if node.left:
        node.path_sum += node.left.path_sum
        node.path_max = max(node.path_max, node.left.path_max)
    if node.right:
        node.path_sum += node.right.path_sum
        node.path_max = max(node.path_max, node.right.path_max)

2. push(node): Lazy 및 rev 처리

def push(node):
    if node.rev:
        node.left, node.right = node.right, node.left
        if node.left:
            node.left.rev ^= True
        if node.right:
            node.right.rev ^= True
        node.rev = False

    if node.lazy_add != 0:
        if node.left:
            apply_lazy(node.left, node.lazy_add)
        if node.right:
            apply_lazy(node.right, node.lazy_add)
        node.lazy_add = 0

def apply_lazy(node, val):
    node.value += val
    node.path_sum += val * node.size
    node.path_max += val
    node.lazy_add += val

📌 lazy_add와 rev는 같이 관리해야 하며,
access → splay → push → update 순서가 필수입니다.

🛠 Path 쿼리 실행 플로우

1. path_sum(u, v)

def path_sum(u, v):
    make_root(u)
    access(v)
    splay(v)
    return v.path_sum

2. path_max(u, v)

def path_max(u, v):
    make_root(u)
    access(v)
    splay(v)
    return v.path_max

3. update_node(u, val)

def update_node(u, val):
    access(u)
    splay(u)
    u.value = val
    update(u)

4. update_path(u, v, add_val)

def update_path(u, v, add_val):
    make_root(u)
    access(v)
    splay(v)
    apply_lazy(v, add_val)

✅ 실전 예시

💡 예: 노드 초기화 및 질의

# 초기화
nodes = [LCTNode(1) for _ in range(5)]
link(nodes[0], nodes[1])
link(nodes[1], nodes[2])
link(nodes[2], nodes[3])

# u–v 경로합
print(path_sum(nodes[0], nodes[3]))  # 4

# u–v 경로 최댓값
print(path_max(nodes[0], nodes[3]))  # 1

# 경로값 일괄 증가
update_path(nodes[0], nodes[3], 2)

# 다시 확인
print(path_sum(nodes[0], nodes[3]))  # 12
print(path_max(nodes[0], nodes[3]))  # 3

📘 실전 문제에서의 활용

문제 번호 활용 포인트

Codeforces 1175F	경로 최대값 유지 + edge 교체
Library Contest – Range LCT	path add + path max 혼합
AtCoder AGC Tree Contest	update_path + path sum

📌 정리 요약

LCT에서 경로 질의는 make_root(u) → access(v) → splay(v) 패턴으로 실행
합, 최댓값, 일괄 변경 등은 push/update/apply_lazy를 제대로 구성하면 모두 가능
Lazy Propagation은 필수 옵션으로 복잡한 쿼리에도 대응 가능

👉 다음 글에서는 Euler Tour Tree 기반의 노드/경로 색칠 및 다이나믹 라벨링 문제를 다루겠습니다.
(예: 경로 중 빨간 노드 개수 구하기, 서브트리 내 라벨 통계 등)

📚 참고자료

CP-Algorithms – Link/Cut Tree augmentation
Sedgewick Algorithms (BST Augmentation Techniques)
Stanford CS166 – Dynamic Tree Applications
Sleator & Tarjan (1985) “Self-adjusting Binary Search Trees with Augmentation”

LinkCutTree, 경로합, 경로최댓값, 트리갱신, LazyPropagation, 동적트리, pathQuery, updatePath, 파이썬알고리즘, SEO 최적화 10개