트리 위에서 exchange argument

Tree Exchange Argument, 트리 위 교환 논증

정의

Exchange Argument (교환 논증) 은 그리디 알고리즘의 최적성 증명 에서 가장 자주 쓰이는 기법. 두 인접 원소를 교환했을 때 답이 나빠지지 않으면, 어떤 정렬 키 가 최적 순서를 정함.

트리 위에서의 exchange argument 는 트리의 부모-자식 또는 형제 순서 를 교환 논증으로 정한 뒤, DP / 그리디 / 우선순위 큐 로 트리를 합쳐 가는 패턴. 1D 의 일반화.

문제 상황과 동기

트리 위 그리디 문제에서 부모-자식 의존 관계 외에는 임의 순서로 노드를 처리할 수 있을 때, 어떤 순서가 최적인가 결정이 까다롭다. 예를 들어 “각 노드마다 비용을 지불하고 보상을 받는데, 부모를 먼저 처리해야 자식을 처리할 수 있다” 는 식의 문제.

Naive 접근: 모든 유효한 처리 순서를 시도 (O(N!) 이상, 불가능) 또는 휴리스틱 greedy 순서 (최적성 보장 불가).

핵심 돌파구: 인접한 두 형제 노드 a, b 의 순서를 바꿨을 때 총 비용이 어떻게 변하는지 식으로 정리하면, 대부분 단순한 비율 비교 (예: a.cost / a.gain vs b.cost / b.gain) 로 귀결된다. 이 비율을 정렬 키로 삼아 priority queue 로 처리하면 O(N log N) 에 최적해 도달.

전형적 응용: 트리 위 자원 배분, 몬스터 처리 순서, 노드 색칠 등 PS 그리디 문제의 고난이도 변형에 등장.

시각화

핵심 아이디어

트리 노드들을 일정 순서로 처리 할 때, 부모-자식 의존 만 지키면 임의 순서 가능. 이 순서를 각 노드의 어떤 score 로 정해 우선순위 큐로 처리.

1. 각 노드 v 에 score(v) 정의 (problem-specific)
2. 부모가 이미 처리된 노드들 중 score 최대인 것 선택
3. 처리 후 자식들이 ready 큐에 추가

핵심 정리: 최적 해에서 두 형제의 순서를 바꾸면 답이 어떻게 변하는가 → 비교 함수 도출.

형제 a 와 b 의 순서 a -> b vs b -> a:
  비용 차이 = f(a, b) - f(b, a)
  이 식을 정리하면 단순 분수 비교 (예: a.cost / a.gain vs b.cost / b.gain)

이 분수가 교환 가능한 비교 키.

응용

1. 01 on Tree (AGC 023 F)

트리 노드에 0/1 이 매겨져 있고, 부모-자식 순서를 지키며 일렬 나열할 때 inversion 최소화. 비교 키 = (1 의 비율).

2. Escape / Monster Hunter

부모-자식 의존 + 자원 / 비용 최적화 게임 류. 비교 키 = cost / gain 비율.

3. Prospecting

채굴 / 비용 / 보상 trade-off. 비슷한 비교 함수.

4. 트리 색칠

자식 노드를 처리할 순서 가 답을 좌우. exchange argument 로 정렬 키.

일반적인 정형

solve(tree):
    각 노드 score 계산
    PQ = [root]
    while PQ not empty:
        v = PQ.pop()  # max score
        부모와 v 를 결합 (parent.merge(v))
        for child of v: PQ.push(child)

부모와 결합하는 방식이 핵심.

구현

다음은 트리 위 exchange argument 의 일반적인 골격. 각 노드의 score 를 계산하고, 부모와 합칠 수 있는 자식들 중 score 가 최대인 것을 먼저 처리한다.

// O(N log N), 트리 위 exchange argument (priority queue 기반 merge)
#include <bits/stdc++.h>
using namespace std;

struct Item {
    double score;     // 문제별 비교 키 (예: gain/cost, 1의비율 등)
    int v;            // 노드 번호
    long long cost;   // 처리 비용
    long long gain;   // 획득 보상
    // 문제에 따라 추가 필드 (subtree size, color count, ...)

    bool operator<(const Item& o) const {
        // max-heap: score 큰 것 우선
        return score < o.score;
    }
};

int N;
vector<int> adj[100005];
long long node_cost[100005];
long long node_gain[100005];

// DFS: 각 서브트리의 score 계산 (문제마다 다름)
// 예시: score = gain / cost 비율
void dfs(int u, int p, priority_queue<Item>& pq) {
    // 리프 또는 서브트리 처리 후 Item 생성
    long long total_cost = node_cost[u];
    long long total_gain = node_gain[u];

    // 자식 서브트리를 재귀적으로 처리
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u, pq);
        // 자식 노드의 결과를 부모와 합침 (구체적 방식은 문제 정의)
    }

    // 이 노드의 score 계산
    double sc = (total_cost == 0) ? 1e18 : (double)total_gain / total_cost;
    pq.push({sc, u, total_cost, total_gain});
}

// 메인 루프: 부모와 합칠 수 있는 자식 중 최대 score 선택
long long solve(int root) {
    priority_queue<Item> pq;
    dfs(root, -1, pq);

    long long answer = 0;
    // pq 에서 하나씩 꺼내 부모와 merge (순서가 답에 영향)
    while (!pq.empty()) {
        Item it = pq.top(); pq.pop();
        // 실제 merge 로직은 문제마다 다름
        // 예: answer += it.cost; 부모의 gain 에 it.gain 추가, 등
        answer += it.cost;
    }

    return answer;
}

int main() {
    cin >> N;
    // 트리 입력, node_cost / node_gain 초기화
    // ...
    cout << solve(1) << "\n";
}

구현 팁

1. score 계산: 문제마다 다르다. 형제 a, b 를 교환했을 때 비용 차이를 식으로 정리해 비율 도출.
2. 부모와의 merge: 자식을 부모에 합칠 때 부모의 cost/gain 도 갱신해야 일관성 유지.
3. overflow 주의: 분수 비교 시 cross multiplication 으로 정수 비교. a/b < c/d → a*d < b*c (단, b, d > 0 가정).
4. tie-break: 같은 score 의 노드들은 임의 순서 또는 추가 키 (ID 등) 로 일관성 확보.

복잡도

작업	비용
score 계산	O(N)
PQ 처리	O(N log N)
부모 결합	보통 O(1) 또는 O(log N)
전체	O(N log N)

함정

1. 비교 함수의 transitivity

a < b, b < c 면 a < c 가 성립해야 정렬이 정확. 분수 형태 비교는 cross multiplication 으로 오버플로 주의.

2. 부모와의 결합

자식 score 가 부모 처리에 영향. 부모 score 를 자식 결합 시 갱신 해야 일관성.

3. 형제의 동률

같은 score 의 형제 처리 순서가 답에 영향. tie-break 명확히.

4. 직관적 비교 키 도출

비교 키는 문제마다 직관 으로 찾아야 함. 예제 직접 비교 → 분수 도출 → 증명 순.

BOJ 연습 문제

번호	제목	링크
BOJ 9539	Escape	kokoa-lab
BOJ 18596	Monster Hunter	kokoa-lab
BOJ 17590	Prospecting	kokoa-lab
BOJ 1763	트리 색칠	kokoa-lab

다른 출처 연습 문제

출처	제목	링크
AtCoder	AGC 023 F (01 on Tree)	https://atcoder.jp/contests/agc023/tasks/agc023_f

참고

• Aliens Trick
• Slope Trick
• 민코프스키 합 DP
• Dynamic Tree