알파카컵 1회: H - 알파카의 컵 보관소

1. 문제 요약

\(N\)개의 정점과 \(N-1\)개의 가중치 있는 간선으로 이루어진 트리가 주어집니다. 각 간선에는 이동 시간(가중치) \(w\)가 있습니다. 처음에는 어느 정점에도 컵 보관소가 없는 상태에서, \(Q\)개의 쿼리를 순서대로 처리해야 합니다.

• 1 x : 정점 \(x\)의 보관소 상태를 토글합니다. 보관소가 없으면 새로 만들고, 있으면 없앱니다.
• 2 x : 정점 \(x\)에서 현재 보관소가 있는 정점들 중 가장 가까운 곳까지의 최단 거리를 출력합니다. 보관소가 하나도 없으면 \(-1\)을 출력합니다.

즉, 동적으로 변하는 정점 집합 \(S\)(보관소가 있는 정점들의 집합)에 대해, 매 질의마다
$$ \text{answer}(x) = \min_{s \in S} \text{dist}(x, s) $$
를 구하는 문제입니다. (\(S\)가 비어 있으면 \(-1\).) 여기서 \(\text{dist}(u, v)\)는 트리에서 두 정점을 잇는 유일한 경로의 가중치 합입니다.

가중치 \(w\)가 최대 \(10^9\)이고 경로에 최대 \(N-1\)개의 간선이 놓일 수 있으므로, 거리는 최대 약 \(2 \times 10^{14}\)까지 커집니다. 반드시 64비트 정수(long long)를 사용해야 합니다.

입력 형식은 다음과 같습니다. 첫 줄에 \(N\ Q\)가 주어지고, 이어지는 \(N-1\)개의 줄에 간선 정보 \(a\ b\ w\)(정점 \(a\)와 \(b\)를 잇는 가중치 \(w\)의 간선)가 주어집니다. 그 뒤 \(Q\)개의 줄에 위의 두 종류 쿼리가 주어집니다.

2. [부분 풀이 1]: 매 질의마다 직접 탐색

가장 직관적인 접근입니다. 보관소의 집합 \(S\)를 bool 배열로 관리하고, 2 x 질의가 들어올 때마다 정점 \(x\)에서 출발하여 트리 전체를 탐색해 가장 가까운 보관소를 직접 찾습니다.

트리에는 음수 간선이 없고, 사실 사이클도 없으므로 단순 BFS/DFS로 모든 정점까지의 거리를 구해도 되지만, 일반적인 가중치 그래프 사고에 익숙해지기 위해 다익스트라(우선순위 큐)로 서술합니다. \(x\)에서 가까운 정점부터 거리를 확정해 나가다가, 처음으로 보관소가 있는 정점을 만나는 순간이 곧 정답입니다. 보관소를 끝까지 만나지 못하면 \(-1\)입니다.

• 풀이: 1 x 쿼리는 mark[x]를 토글하는 것으로 \(O(1)\)에 처리합니다. 2 x 쿼리는 \(x\)를 시작점으로 다익스트라(트리이므로 BFS여도 무방)를 돌려, 거리가 확정되는 정점이 보관소이면 즉시 그 거리를 답으로 출력하고 종료합니다. 큐가 빌 때까지 보관소를 못 찾으면 \(-1\)을 출력합니다.

• 시간 복잡도: 질의 한 번에 트리 전체를 보므로 \(O(N \log N)\)(또는 BFS로 \(O(N)\))이 걸립니다. 전체 \(O(Q \cdot N \log N)\)로, \(N, Q \le 2 \times 10^5\)에서는 \(10^{10}\)을 한참 넘어 시간 초과입니다. 작은 입력에서 정답을 검증하는 용도로만 유효합니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
using ll = long long;
using pli = pair<ll, int>;
int n, q;
vector<pli> v[200001];
bool mark[200001];
int main() {
    fastio
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int a, b; ll w;
        cin >> a >> b >> w;
        v[a].push_back({w, b});
        v[b].push_back({w, a});
    }
    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            mark[x] = !mark[x];
        } else {
            vector<ll> dist(n + 1, LLONG_MAX);
            priority_queue<pli, vector<pli>, greater<pli>> pq;
            dist[x] = 0;
            pq.push({0, x});
            ll ans = -1;
            while (!pq.empty()) {
                auto [d, u] = pq.top();
                pq.pop();
                if (d > dist[u]) continue;
                if (mark[u]) { ans = d; break; }
                for (auto [w, nx] : v[u]) {
                    if (dist[u] + w < dist[nx]) {
                        dist[nx] = dist[u] + w;
                        pq.push({dist[nx], nx});
                    }
                }
            }
            cout << ans << endl;
        }
    }
}

3. [부분 풀이 2]: 보관소가 적거나 질의가 적은 경우

부분 풀이 1이 느린 이유는 매 질의마다 트리 전체를 훑기 때문입니다. 한 가지 자연스러운 개선은 "거리는 항상 보관소 쪽에서 계산한다"는 관점입니다.

만약 현재 보관소의 개수 \(|S|\)가 작다면, \(x\)에서 모든 보관소까지 일일이 거리를 구하는 편이 더 빠릅니다. 트리에서 두 정점의 거리는 \(\text{LCA}\)(최소 공통 조상)를 이용해 다음과 같이 \(O(\log N)\)에 구할 수 있습니다.
$$ \text{dist}(u, v) = \text{depthSum}[u] + \text{depthSum}[v] - 2 \cdot \text{depthSum}[\text{LCA}(u, v)] $$
여기서 \(\text{depthSum}[u]\)는 루트에서 \(u\)까지의 가중치 합입니다. 희소 배열(sparse table)로 \(\text{LCA}\)를 전처리해 두면, 2 x 질의는 현재 보관소 각각에 대해 거리를 계산해 최솟값을 취하는 것으로 처리됩니다.

• 풀이: \(\text{LCA}\)용 희소 배열과 루트로부터의 누적 거리 \(\text{depthSum}\)을 전처리합니다(1 기반 깊이). 보관소 집합 \(S\)를 따로 들고 다니며, 1 x는 \(S\)에 \(x\)를 넣거나 빼고, 2 x는 \(S\)의 모든 원소 \(s\)에 대해 \(\text{dist}(x, s)\)를 계산해 최솟값을 출력합니다(\(S\)가 비면 \(-1\)).

• 시간 복잡도: 2 x 질의 한 번에 \(O(|S| \log N)\). 보관소가 매우 적거나 질의 수가 적을 때만 통과합니다. 최악의 경우 보관소가 \(O(N)\)개라면 질의당 \(O(N \log N)\)이 되어 부분 풀이 1과 다를 바 없습니다. "거리를 보관소 집합 위에서 본다"는 발상은 정해로 가는 다리가 됩니다. 핵심은 이 \(\min\) 연산을 어떻게 트리 구조를 활용해 매번 \(O(N)\)이 아니라 \(O(\text{polylog})\)로 줄이느냐입니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
using ll = long long;
const int LOG = 18;
int n, q;
vector<pair<int, ll>> v[200001];
int up[LOG][200001], dep[200001];
ll depthSum[200001];
void dfs(int x, int p) {
    up[0][x] = p;
    for (int j = 1; j < LOG; j++) up[j][x] = up[j - 1][up[j - 1][x]];
    for (auto [nx, w] : v[x]) if (nx != p) {
        dep[nx] = dep[x] + 1;
        depthSum[nx] = depthSum[x] + w;
        dfs(nx, x);
    }
}
int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    int diff = dep[a] - dep[b];
    for (int j = LOG - 1; j >= 0; j--) if ((diff >> j) & 1) a = up[j][a];
    if (a == b) return a;
    for (int j = LOG - 1; j >= 0; j--) if (up[j][a] != up[j][b]) { a = up[j][a]; b = up[j][b]; }
    return up[0][a];
}
ll dist(int a, int b) { return depthSum[a] + depthSum[b] - 2 * depthSum[lca(a, b)]; }
set<int> S;
int main() {
    fastio
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int a, b; ll w;
        cin >> a >> b >> w;
        v[a].push_back({b, w});
        v[b].push_back({a, w});
    }
    dep[1] = 0;
    dfs(1, 1);
    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            if (S.count(x)) S.erase(x);
            else S.insert(x);
        } else {
            if (S.empty()) { cout << -1 << endl; continue; }
            ll ans = LLONG_MAX;
            for (int s : S) ans = min(ans, dist(x, s));
            cout << ans << endl;
        }
    }
}

4. 정해: 센트로이드 분할 (Centroid Decomposition)

부분 풀이 2에서 본 "거리를 보관소 집합 위에서 \(\min\)으로 본다"는 관점을, 센트로이드 분할로 자료구조화하면 질의·갱신을 모두 \(O(\log^2 N)\)에 처리할 수 있습니다.

센트로이드 분할이란

트리의 센트로이드(무게중심) 는, 그 정점을 제거했을 때 분리되는 모든 서브트리의 크기가 전체의 절반 이하가 되는 정점입니다. 센트로이드를 찾아 제거하면 트리는 각각 크기가 절반 이하인 조각들로 나뉩니다. 각 조각에 대해 이 과정을 재귀적으로 반복하면, 정점들 사이에 센트로이드 트리라는 보조 트리가 만들어집니다.

이 센트로이드 트리의 핵심 성질은 높이가 \(O(\log N)\) 이라는 점입니다. 따라서 원래 트리의 어떤 정점 \(x\)를 잡아도, 센트로이드 트리에서 \(x\)의 조상(자기 자신 포함)은 \(O(\log N)\)개뿐입니다. 이 조상들을 \(x\)의 센트로이드 조상이라 부릅니다.

가장 중요한 사실은 다음과 같습니다.

원래 트리에서 임의의 두 정점 \(u, v\) 사이의 경로는, 센트로이드 트리에서 \(u\)와 \(v\)의 공통 센트로이드 조상 중 적어도 하나(구체적으로는 둘의 LCA가 되는 센트로이드 \(c\))를 반드시 지난다.

따라서 \(\text{dist}(u, v) = \text{dist}(u, c) + \text{dist}(c, v)\)가 그 \(c\)에서 성립합니다. 즉, 모든 경로를 "어떤 센트로이드를 경유하는 경로"로 분해해 관리할 수 있습니다.

센트로이드마다 multiset 들기

각 센트로이드 \(c\)에 대해, 그 시점에 보관소가 켜져 있고 \(c\)를 센트로이드 조상으로 갖는 정점들의, \(c\)까지의 거리들을 모아 둔 multiset(다중집합) \(\text{ms}[c]\)를 유지합니다.

• 토글 1 x: \(x\)의 모든 센트로이드 조상 \(c\)에 대해, 보관소를 켜는 경우 \(\text{dist}(x, c)\)를 \(\text{ms}[c]\)에 삽입하고, 끄는 경우 그 값을 하나 제거합니다. 조상이 \(O(\log N)\)개이므로 갱신은 \(O(\log N)\)번의 multiset 연산입니다.

• 질의 2 x: \(x\)의 각 센트로이드 조상 \(c\)에 대해 후보값 \(\text{dist}(x, c) + \min(\text{ms}[c])\)를 계산하고(단 \(\text{ms}[c]\)가 비어 있지 않을 때만), 이 후보들의 최솟값을 답으로 합니다. 모든 조상의 \(\text{ms}\)가 비어 있으면 \(-1\)입니다.

이것이 올바른 이유: 임의의 보관소 \(s\)와 질의점 \(x\) 사이의 최단 거리 경로는 어떤 공통 센트로이드 조상 \(c\)를 지나며, 그때 \(\text{dist}(x, s) = \text{dist}(x, c) + \text{dist}(c, s)\)입니다. 우리는 그 \(c\)에서 \(\text{dist}(c, s)\)를 \(\text{ms}[c]\)에 이미 넣어 두었으므로, \(c\)의 후보 \(\text{dist}(x, c) + \min(\text{ms}[c]) \le \text{dist}(x, c) + \text{dist}(c, s) = \text{dist}(x, s)\)로 정답을 놓치지 않습니다. 반대로, 어떤 후보값도 실제로 존재하는 어떤 보관소까지의 (경유 경로) 거리이므로 실제 최단 거리보다 작아질 수 없습니다. 따라서 후보들의 최솟값이 정확히 정답입니다. (경유 경로의 길이는 직선 경로 길이 이상이지만, 정답을 주는 \(c\)에서는 등호가 성립하므로 최솟값은 정확합니다.)

-1 처리: 모든 토글이 정확히 대칭으로 삽입/삭제되므로, 보관소가 하나도 없을 때는 모든 \(\text{ms}[c]\)가 비어 있어 어떤 후보도 만들어지지 않고 자연스럽게 \(-1\)이 출력됩니다.

dist(x, 센트로이드 조상) 빠르게 구하기

\(\text{dist}(x, c)\)가 필요한데, 매번 LCA를 호출해도 \(O(\log N)\)이라 전체 \(O(\log^2 N)\)으로 충분합니다. 다만 상수를 줄이기 위해, 분할 과정에서 각 센트로이드 \(c\)로부터 그 조각 안의 모든 정점까지의 거리를 한 번의 DFS로 미리 계산해 둘 수 있습니다. 정점 \(x\)마다 센트로이드 조상별 거리를 깊이 순서대로 배열 \(\text{distc}[x]\)에 저장해 두면, 토글·질의에서 곧바로 \(O(1)\)에 꺼내 쓸 수 있습니다. 아래 구현은 이 방식을 사용합니다.

구현 주의점:
- 분할은 반드시 현재 조각의 크기를 다시 센 뒤 센트로이드를 찾아야 합니다. (이미 제거된 정점은 removed로 건너뜁니다.)
- 센트로이드 조상까지의 거리는 \(10^{14}\)급이므로 long long으로 다룹니다.
- multiset에서 같은 값이 여러 번 들어갈 수 있으므로, 삭제는 반드시 find로 하나의 반복자만 지운 뒤 erase(it)해야 합니다. erase(value)는 같은 값을 전부 지우므로 사용하면 안 됩니다.
- \(N\)이 최대 \(2 \times 10^5\)이고 트리가 일자(path) 형태일 수 있으므로, 크기 계산·센트로이드 탐색·거리 수집을 재귀 DFS로 짜면 깊이가 \(2 \times 10^5\)에 달해 스택 오버플로(런타임 에러) 가 납니다. 아래 구현은 이 모든 과정을 명시적 스택/큐 기반의 반복(iterative) DFS로 작성해 안전하게 처리합니다. (또는 컴파일러·채점 환경에서 스택 크기를 충분히 키워야 합니다.)

• 풀이: 위 설명대로, (1) 센트로이드 분할로 센트로이드 트리(부모 cpar, 깊이 cdep)와 각 정점의 센트로이드 조상별 거리 distc를 전처리하고, (2) 1 x는 \(x\)의 모든 센트로이드 조상의 multiset에 거리를 삽입/삭제, (3) 2 x는 그 조상들에서 (거리 + multiset 최솟값)의 최솟값을 출력합니다.

• 시간 복잡도: 분할 전처리는 각 정점이 \(O(\log N)\)개의 조각에 속하므로 \(O(N \log N)\)입니다. 토글·질의는 모두 \(O(\log N)\)개의 센트로이드 조상을 순회하며 각각 \(O(\log N)\)의 multiset 연산(또는 \(O(1)\)의 거리 조회 + 최솟값 조회)을 하므로 쿼리당 \(O(\log^2 N)\)입니다. 전체 \(O((N + Q) \log^2 N)\)로 제한 안에 통과합니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
using ll = long long;
const int MAXN = 200005;
int n, q;
vector<pair<int, ll>> v[MAXN];
bool removed[MAXN];
int sz[MAXN], par_[MAXN];
int cpar[MAXN];          // 센트로이드 트리에서의 부모 (루트는 -1)
int cdep[MAXN];          // 센트로이드 트리에서의 깊이 (루트 = 0)
vector<ll> distc[MAXN];  // distc[x][d] = (cdep가 d인 x의 센트로이드 조상)까지의 거리
multiset<ll> ms[MAXN];    // 센트로이드 c에 모인, 켜져 있는 보관소까지의 거리들
bool mark[MAXN];
int order_[MAXN], ocnt;  // 반복 DFS 방문 순서 버퍼
// 반복 DFS로 현재 조각의 크기 계산 (역순으로 누적), root 크기 반환
int buildSizes(int root) {
    ocnt = 0;
    order_[ocnt++] = root; par_[root] = -1;
    for (int i = 0; i < ocnt; i++) {
        int x = order_[i];
        for (auto [nx, w] : v[x]) if (nx != par_[x] && !removed[nx]) {
            par_[nx] = x;
            order_[ocnt++] = nx;
        }
    }
    for (int i = ocnt - 1; i >= 0; i--) {
        int x = order_[i];
        sz[x] = 1;
        for (auto [nx, w] : v[x]) if (nx != par_[x] && !removed[nx]) sz[x] += sz[nx];
    }
    return sz[root];
}
// 절반 초과 자식 쪽으로 내려가며 센트로이드를 반복적으로 탐색
int findCent(int root, int tot) {
    int x = root, p = -1;
    while (true) {
        int nxt = -1;
        for (auto [nx, w] : v[x]) if (nx != p && !removed[nx] && sz[nx] > tot / 2) { nxt = nx; break; }
        if (nxt == -1) return x;
        p = x; x = nxt;
    }
}
// 반복 DFS로 센트로이드 c에서 조각 내 모든 정점까지 거리를 distc에 추가
// (분할 순서상 조상이 항상 깊이 순으로 먼저 들어오므로, push_back 인덱스 = cdep)
void gather(int c) {
    int cnt = 0;
    order_[cnt++] = c; par_[c] = -1; distc[c].push_back(0);
    for (int i = 0; i < cnt; i++) {
        int x = order_[i];
        ll dx = distc[x].back();
        for (auto [nx, w] : v[x]) if (nx != par_[x] && !removed[nx]) {
            par_[nx] = x;
            distc[nx].push_back(dx + w);
            order_[cnt++] = nx;
        }
    }
}
// 명시적 스택 기반 센트로이드 분할
void decomposeAll() {
    stack<tuple<int, int, int>> st;  // (조각 진입점, 센트로이드 트리 부모, 깊이)
    st.push({1, -1, 0});
    while (!st.empty()) {
        auto [entry, par, dpt] = st.top(); st.pop();
        int tot = buildSizes(entry);
        int c = findCent(entry, tot);
        cpar[c] = par; cdep[c] = dpt;
        removed[c] = true;
        gather(c);
        for (auto [nx, w] : v[c]) if (!removed[nx]) st.push({nx, c, dpt + 1});
    }
}
void toggle(int x) {
    mark[x] = !mark[x];
    int cur = x;
    if (mark[x]) {
        while (cur != -1) { ms[cur].insert(distc[x][cdep[cur]]); cur = cpar[cur]; }
    } else {
        while (cur != -1) {
            auto it = ms[cur].find(distc[x][cdep[cur]]);
            ms[cur].erase(it);
            cur = cpar[cur];
        }
    }
}
ll queryNode(int x) {
    ll ans = -1;
    int cur = x;
    while (cur != -1) {
        if (!ms[cur].empty()) {
            ll cand = distc[x][cdep[cur]] + *ms[cur].begin();
            if (ans == -1 || cand < ans) ans = cand;
        }
        cur = cpar[cur];
    }
    return ans;
}
int main() {
    fastio
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int a, b; ll w;
        cin >> a >> b >> w;
        v[a].push_back({b, w});
        v[b].push_back({a, w});
    }
    decomposeAll();
    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) toggle(x);
        else cout << queryNode(x) << endl;
    }
}

첫 번째 예제로 따라가 보기

트리는 간선 \(1\!-\!2\,(3)\), \(1\!-\!3\,(2)\), \(2\!-\!4\,(4)\), \(2\!-\!5\,(1)\)로 이루어집니다.
- 2 1 : 아직 보관소가 없으므로 \(-1\).
- 1 4 : 정점 4에 보관소 생성.
- 2 5 : 5에서 가장 가까운 보관소는 4이고 \(5 \to 2 \to 4 = 1 + 4 = 5\). 답 \(5\).
- 1 3 : 정점 3에 보관소 생성. (이제 보관소 = \(\{3, 4\}\).)
- 2 5 : 5에서 4까지는 \(5\), 5에서 3까지는 \(5 \to 2 \to 1 \to 3 = 1 + 3 + 2 = 6\). 최솟값 \(5\).
- 2 1 : 1에서 3까지 \(2\), 1에서 4까지 \(3 + 4 = 7\). 최솟값 \(2\).
- 1 4 : 정점 4의 보관소 제거. (보관소 = \(\{3\}\).)
- 2 5 : 5에서 3까지 \(6\). 답 \(6\).
- 1 3 : 정점 3 제거(이후 질의 없음).

출력은 -1 5 5 2 6으로 예제와 일치합니다. 센트로이드 분할은 이 과정을 정점 수에 무관하게 쿼리당 \(O(\log^2 N)\)으로 처리합니다.

아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.