[Algorithm] cpp 백준 5820번: 경주 - 길이 K 최소 간선 경로

문제

링크: https://www.acmicpc.net/problem/5820
요약: N개의 도시와 N-1개의 양방향 고속도로(트리)에서 길이 합이 정확히 K인 단순 경로 중 사용 간선 수가 최소인 것을 찾는다. 없으면 -1을 출력한다.

제한/스펙

1 ≤ N ≤ 200000, 1 ≤ K ≤ 1000000
간선 가중치 0 ≤ w ≤ 1e6 (정수), 트리 구조(임의 두 점 사이 경로 유일)
시간 제한 3초 → O(N log N) 수준 설계 필요

입출력 형식/예제

예제 입력 1

예제 출력 1

1
2

접근 개요(아이디어 스케치)

핵심 관찰: 경로 길이 합이 정확히 K가 되도록 두 구간 거리 d와 K−d를 합쳐 만들면 된다. 트리에서 이를 전역적으로 빠르게 찾으려면 한 분할 중심에서 모든 자식 서브트리의 거리 목록을 수집해 “보완 거리"를 즉시 매칭하면 된다.
전략: 센트로이드 분해. 센트로이드를 기준으로 각 자식 서브트리의 (거리, 사용 간선 수) 목록을 DFS로 수집하고, 이전까지 처리한 서브트리들의 거리 버킷 bestDist[dist](해당 거리를 만드는 최소 간선 수)에 대해 need = K - d를 O(1)로 조회하여 후보 답을 갱신한다. 그 후 현재 서브트리의 거리 정보를 bestDist에 병합한다.
최적화: bestDist는 길이 K+1 배열이지만, 실제로 갱신된 인덱스만 touched에 기록했다가 한 센트로이드 처리가 끝나면 해당 인덱스만 초기화하여 O(방문 수)로 관리한다.

flowchart TD
  C[센트로이드 선택] --> S1[각 자식 서브트리 DFS로 (거리 d, 간선 e) 수집]
  S1 --> Q[need = K - d 조회로 즉시 매칭]
  Q --> U[bestDist[need] + e 로 최소 간선 갱신]
  U --> M[현재 서브트리의 (d,e) 들을 bestDist 에 병합]
  M --> N[다음 자식 처리]
  N -->|모두 처리| R[터치된 거리만 초기화]
  R --> D[차단 후 남은 컴포넌트 재귀 분해]

알고리즘 설계

상태
- bestDist[0..K]: 해당 거리 달성에 필요한 최소 간선 수(미설정은 INF).
- touched: 현 센트로이드 처리 중 갱신한 거리 인덱스 목록.
절차(센트로이드 c 기준)
1. bestDist[0] = 0으로 시작(경로가 c에서 끊기는 경우).
2. 각 자식 서브트리에서 DFS로 (dist, edges)를 수집(누적 거리가 K를 넘으면 가지치기).
3. 수집된 각 (d,e)에 대해 need = K - d; bestDist[need]가 유효하면 ans = min(ans, bestDist[need] + e).
4. 그 후 현재 서브트리의 (d,e)를 bestDist[d] = min(bestDist[d], e)로 병합. 이때 처음 갱신하는 d는 touched에 기록.
5. 모든 자식 처리 후 touched에 한해 bestDist를 INF로 복원.
6. 센트로이드를 차단하고 각 남은 컴포넌트에 대해 재귀.
올바름 근거
- 모든 경로는 어떤 센트로이드 c를 반드시 지난다. 그 경로는 c 기준으로 서로 다른 두 서브트리 경로(또는 하나의 서브트리와 빈 경로)로 분해되며, 길이 합이 K가 되는 두 거리 d와 K−d의 조합으로 표현된다. 각 서브트리를 순차 처리하며 기존 bestDist와의 매칭은 서로 다른 서브트리 쌍만 결합하게 되어 중복/자기결합이 없다.
- 각 거리에서 최소 간선 수만 유지하므로 최종적으로 최소 간선 수가 도출된다.

복잡도

시간: 각 간선이 O(log N) 레벨의 센트로이드에서 한 번씩 수집/매칭되므로 총 O(N log N).
공간: 그래프 O(N), bestDist O(K)(최대 약 1e6+1), touched는 방문 수 만큼.

구현 (C++)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

static const int INF = 1e9;

int N, K;
vector<vector<pair<int,int>>> graphEdges;
vector<int> subtreeSize;
vector<char> isBlocked;

vector<int> bestDist;         // bestDist[distance] = minimal edges to achieve this distance (from previous children)
vector<int> touchedDistances; // indices in bestDist that we set during current centroid processing

int answerMinEdges = INF;

int computeSubtreeSize(int node, int parent) {
    subtreeSize[node] = 1;
    for (const auto &edge : graphEdges[node]) {
        int next = edge.first;
        if (next == parent || isBlocked[next]) continue;
        subtreeSize[node] += computeSubtreeSize(next, node);
    }
    return subtreeSize[node];
}

int findCentroid(int node, int parent, int totalSize) {
    for (const auto &edge : graphEdges[node]) {
        int next = edge.first;
        if (next == parent || isBlocked[next]) continue;
        if (subtreeSize[next] * 2 > totalSize) {
            return findCentroid(next, node, totalSize);
        }
    }
    return node;
}

void collectDistances(int node, int parent, int dist, int edgesUsed, vector<pair<int,int>> &buffer) {
    if (dist > K) return;
    buffer.emplace_back(dist, edgesUsed);
    for (const auto &edge : graphEdges[node]) {
        int next = edge.first, w = edge.second;
        if (next == parent || isBlocked[next]) continue;
        int nd = dist + w;
        if (nd > K) continue; // prune
        collectDistances(next, node, nd, edgesUsed + 1, buffer);
    }
}

void decompose(int entry) {
    int total = computeSubtreeSize(entry, -1);
    int centroid = findCentroid(entry, -1, total);
    isBlocked[centroid] = 1;

    // Initialize bestDist for this centroid (distance 0 with 0 edges at the centroid itself)
    if (bestDist[0] == INF) touchedDistances.push_back(0);
    bestDist[0] = 0;

    // Process each child subtree: query against bestDist (paths via centroid), then insert this subtree's distances
    for (const auto &edge : graphEdges[centroid]) {
        int child = edge.first, w = edge.second;
        if (isBlocked[child]) continue;

        vector<pair<int,int>> collected;
        if (w <= K) collectDistances(child, centroid, w, 1, collected);

        for (const auto &p : collected) {
            int d = p.first, e = p.second;
            int need = K - d;
            if (need < 0) continue;
            if (bestDist[need] != INF) {
                answerMinEdges = min(answerMinEdges, bestDist[need] + e);
            }
        }
        for (const auto &p : collected) {
            int d = p.first, e = p.second;
            if (bestDist[d] == INF) touchedDistances.push_back(d);
            if (bestDist[d] > e) bestDist[d] = e;
        }
    }

    // Clear bestDist updates for this centroid
    for (int d : touchedDistances) bestDist[d] = INF;
    touchedDistances.clear();

    // Recurse on remaining components
    for (const auto &edge : graphEdges[centroid]) {
        int child = edge.first;
        if (!isBlocked[child]) decompose(child);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> N >> K)) return 0;
    graphEdges.assign(N, {});
    for (int i = 0; i < N - 1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        graphEdges[a].push_back({b, w});
        graphEdges[b].push_back({a, w});
    }

    subtreeSize.assign(N, 0);
    isBlocked.assign(N, 0);
    bestDist.assign(K + 1, INF);
    touchedDistances.reserve(1 << 16);

    decompose(0);

    cout << (answerMinEdges == INF ? -1 : answerMinEdges) << '\n';
    return 0;
}