[응용편] Link/Cut Tree에 경로 합, 경로 최댓값 추가하기 – Augmented LCT 구현

[응용편] Link/Cut Tree에 경로 합, 경로 최댓값 추가하기 – Augmented LCT 구현

앞선 글에서는 Link/Cut Tree(LCT)의 **핵심 구조와 기본 연산(link, cut, access)**을 Python으로 직접 구현해보았습니다.
이번에는 한 단계 더 나아가서,
LCT 노드에 값을 부여하고 경로의 합이나 최댓값을 빠르게 계산할 수 있는 구조로 확장해보겠습니다.

---

✨ 목표: 경로 질의가 가능한 LCT

기본 LCT는 access(u), make_root(u), link(u, v) 등을 수행할 수는 있지만,
실제로는 경로 상의 합/최댓값/최솟값을 빠르게 계산해야 할 일이 많습니다.

예: "u부터 v까지 간선 가중치의 합은?", "가장 큰 값은?"

이 기능을 위해 우리는 LCT 노드에 다음 정보를 추가합니다:

class Node:
    def __init__(self, id, value=0):
        self.id = id
        self.left = None
        self.right = None
        self.parent = None
        self.reversed = False
        
        # Augmented 정보
        self.value = value            # 자기 자신의 값
        self.sum = value              # 서브트리 전체의 합
        self.max_val = value          # 서브트리 최대값

---

🔁 보조 연산 추가

📌 1. update(x): 현재 노드의 합/최댓값 갱신

def update(x):
    x.sum = x.value
    x.max_val = x.value
    if x.left:
        x.sum += x.left.sum
        x.max_val = max(x.max_val, x.left.max_val)
    if x.right:
        x.sum += x.right.sum
        x.max_val = max(x.max_val, x.right.max_val)

📌 2. push(x): 뒤집기 (Lazy Propagation)

def push(x):
    if x.reversed:
        x.left, x.right = x.right, x.left
        if x.left:
            x.left.reversed ^= True
        if x.right:
            x.right.reversed ^= True
        x.reversed = False

---

🧠 Splay 연산에 보조 연산 통합

🔄 splay(x)에 push()와 update() 추가:

반응형

def splay(x):
    stack = []
    y = x
    while not is_root(y):
        stack.append(y)
        y = y.parent
    stack.append(y)
    while stack:
        push(stack.pop())
    
    while not is_root(x):
        p = x.parent
        g = p.parent
        if not is_root(p):
            if (p.left == x) == (g.left == p):
                rotate(p)
            else:
                rotate(x)
        rotate(x)
    update(x)

---

✅ 경로 질의 사용법

이제 다음과 같이 make_root(u), access(v)를 한 뒤 v.sum 또는 v.max_val로
u-v 경로의 합 또는 최댓값을 바로 확인할 수 있습니다.

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

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

---

🔧 테스트 예시

nodes = [Node(i, value=i) for i in range(5)]

link(nodes[0], nodes[1])
link(nodes[1], nodes[2])
link(nodes[2], nodes[3])

print(path_sum(nodes[0], nodes[3]))  # 0 + 1 + 2 + 3 = 6
print(path_max(nodes[0], nodes[3]))  # max(0,1,2,3) = 3

---

📘 다음 목표

• 경로 업데이트 (예: u-v 경로에 +5 추가)
• Lazy Propagation 확장
• 동적 MST 유지 문제 적용 예제 풀이

이제 LCT는 정적인 HLD나 ETT로는 처리할 수 없는
실시간 연결 변화, 경로 단위 최적화, 가중치 롤백 등에 적합한 자료구조가 됩니다.

---

 

LinkCutTree응용, 트리경로합, LCT확장버전, pathSum, pathMax, 동적트리업데이트, SplayTreeAugment, 파이썬알고리즘, 알고리즘트리강의, SEO 최적화 10개