Euler Tour Tree 기반 노드 색칠 및 라벨 통계 처리: 서브트리와 경로에 색 정보를 효율적으로 반영하기

이번 글에서는 **Euler Tour Tree (ETT)**를 기반으로
**노드의 색칠(라벨링)**이나 색별 통계 집계를
효율적으로 처리하는 방법을 소개합니다.

이는 트리 기반 소셜 네트워크, 유저 상태 관리, 서브트리 질의에서
자주 등장하는 문제로, ETT 구조에 세그먼트 트리, Lazy Propagation을 결합하여 해결합니다.

✅ 예제 문제 유형

paint(u, color)
→ 노드 u의 색을 변경
count_color(u, c)
→ u의 서브트리에서 색 c를 가진 노드의 수
path_color_freq(u, v, c)
→ u–v 경로상에서 색 c를 가진 노드의 수

🧠 핵심 아이디어: Euler Tour + Segment Tree

오일러 투어를 통해 트리를 배열로 변환:
in[u], out[u]로 서브트리 구간 표현 가능
색 정보를 배열 인덱스에 매핑
각 색상마다 BIT or Segment Tree를 하나씩 만들어
구간 쿼리 가능하게 구성

🛠 단계별 구현 전략

1. 오일러 투어 + 인덱싱

in_time = [0] * n
out_time = [0] * n
tour = []
time = 0

def dfs(u, p):
    global time
    in_time[u] = time
    tour.append(u)
    time += 1
    for v in tree[u]:
        if v != p:
            dfs(v, u)
    out_time[u] = time
    tour.append(u)
    time += 1

in_time[u] ~ out_time[u]까지가 서브트리 구간이 됨 (Euler Tour 2번 등장)

2. 색상별 Fenwick Tree 또는 Segment Tree 구성

class BIT:
    def __init__(self, n):
        self.N = n + 2
        self.tree = [0] * self.N

    def add(self, i, x):
        i += 1
        while i < self.N:
            self.tree[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l - 1)

3. 색칠 및 쿼리 처리

color_bit = defaultdict(lambda: BIT(2 * n))  # 각 색마다 BIT

def paint(u, new_color):
    old_color = node_color[u]
    pos = in_time[u]
    color_bit[old_color].add(pos, -1)
    color_bit[new_color].add(pos, 1)
    node_color[u] = new_color

def count_color_subtree(u, color):
    l = in_time[u]
    r = out_time[u]
    return color_bit[color].range_sum(l, r)

✅ 경로 쿼리 처리 (path_color_freq)

Euler Tour Tree 기반에서는 Segment Tree + LCA 활용 또는
Link/Cut Tree에서 경로 추출 후 색 개수 집계로 구현 가능.

복잡도 측면에서는 일반적으로:

정적 트리라면 → Heavy-Light Decomposition + Segment Tree
동적 트리라면 → ETT + BIT 구조 or LCT + Augmented Node

📘 응용 문제 예시

문제 내용

백준 24230	트리 색칠 최소 변경 횟수
AtCoder ABC 222E	트리 경로의 색상 분포 통계
Codeforces 1328E	노드 색별 경로 존재 판별

✅ 정리 요약

트리의 색 분포/라벨 통계 문제는 ETT + 세그먼트 트리로 풀 수 있다.
Euler Tour를 통해 트리를 배열처럼 다루면,
서브트리 구간 질의가 단순한 Range Query로 변환된다.
색별로 BIT/Segment Tree를 구성해 빠르게 색 정보를 집계할 수 있다.

👉 다음 글에서는 **Heavy-Light Decomposition(HLD)**으로
경로상의 값 변경/질의를 고속 처리하는 방법을 설명합니다.

📚 참고자료

CP-Algorithms – Tree queries
AtCoder Typical DP Contest – 색분포 문제
IOI/JOI 경로 라벨링 문제 해설
cp-algorithms.com/graph/euler-tour-technique.html

EulerTourTree, 색칠문제, 라벨통계, 트리쿼리, 서브트리색상, 트리색분포, SegmentTree, BIT, 파이썬알고리즘, SEO 최적화 10개