백준 21033 - Sending Blessings (C++)

문제

• 문제 링크

  
   BOJ 21033 - Sending Blessings 
  

• 문제 요약

$N$개의 정점과 이들을 잇는 $N$개의 간선이 주어진다.
$Q$개의 쿼리에 대해 알맞는 답을 출력해보자.

• 제한

TL : $2$ sec, ML : $512$ MB




$3 ≤ N ≤ 10^5$

$1 ≤ Q, C_i ≤ 10^5$

알고리즘 분류

• 자료 구조(data structures)
• 트리(trees)
• 구현(implementation)
• 세그먼트 트리(segment tree)
• 최소 공통 조상(lowest common ancestor)
• 희소 배열(sparse table)

풀이

$N$개의 간선으로 이루어진 그래프 즉, 사이클이 내포된 $Unicycle$ $Graph$ 에서 사이클을 분리하는 방법을 아는가?
이에 익숙치 않다면 다음 두 문제 정도 선행해 보는 것을 추천한다.

BOJ 20530 - 양분
BOJ 26262 - 트리 더하기

$Unicycle$ $Graph$에서 사이클을 찾았다면, 주어진 그래프를 "사이클에 속한 $G_1, G_2, ... G_k$ 정점을 루트로 하는 $k$개의 트리"로 바라볼 수 있다.

각 트리마다 $G_i$를 명시하여 그룹을 지어줌과 동시에 $LCA$를 위한 기초 전처리를 함께 진행하자.
사이클 분리를 마쳤다면 이제 쿼리에 대한 $case$_$work$ 를 진행 해보자.

---

나는 다음의 세 경우로 관찰 하였다.

1. $i, j$가 같은 그룹에 속할 경우
2. $i$ == $G[i]$ && $j$ == $G[j]$ 임에 따라 $G_i$ 에서 $G_j$로 이동하는 경우.
3. 서로 다른 그룹에 속하면서, 최소 한 정점이 사이클에 속하지 않는 경우.

---

첫번째 경우.

이는 간단하게 $LCA$ 및 같은 시점의 최소 가중치를 저장하는 희소 배열을 이용해 쉽게 구할 수 있다.

두번째 및 세번째 경우.

이 경우는 사이클에 대하여 다음의 질문으로 환원 시켜 생각해 볼 수 있다.

임의의 두 점 $G_i, G_j$를 잇는 시계 / 반시계 경로 각각에서의 최소 가중치를 $O(logN)$만에 찾아낼 수 있는가?

척 보면 최솟값 세그먼트 트리로 쉽게 해결할 수 있을 듯 싶다.
구체적으로, 사이클 위 정점들의 새로 메겨진 번호를 $rev_1, rev_2, ... rev_k$라 해보자.
그리고 각 정점마다 그 정점으로 들어오는 간선의 가중치를 메겨 줬다고 생각해보자.

그럼 $G_i, G_j$에 대해 $rev[G_i] < rev[G_j]$ 를 만족하도록 일반성을 유지 한다고 할 때,

• 정방향 최솟값은 $[rev[G_i] + 1, rev[G_j]]$ 의 범위에서의 최솟값을 취하면 된다. ( $V_1$ )
• 역방향 최솟값은 $min([1, rev[G_i]], [rev[G_j] + 1, k])$ 의 값을 취하면 된다. ( $V_2$ )

이에 따라 두번째 경우에는, 간단히 $V_1 + V_2$ 의 값이 답이 됨을 알 수 있다.

세번째 경우에는, $V_1 + V_2$ 의 값이 전부가 아니다.
사이클을 지나 시작점인 $i$ 또는 $j$까지 가는 데에 지나는 간선들의 가중치 역시 신경 써야 하기 때문이다.

사이클을 제외한 경로에서의 최솟값은 첫번째 경우처럼 희소 배열을 이용해 쉽게 구할 수 있으므로,
답은 $min(V_1 + V_2, min(LCA(i, G_i), LCA(j, G_j)))$ 가 되겠다.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
vector <pair<int, int>> Gr[N];
vector <int> arr(1);
int C[N], G[N], Cy[N];
int D[N], dp[N][18], mdp[N][18];
int rev[N], seg[1 << 18];
int n, q, k;
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int o{}, i, j, w; o++ < n; C[i]++, C[j]++)
    {
        cin >> i >> j >> w;
        Gr[i].emplace_back(j, w), Gr[j].emplace_back(i, w);
    }
}
void CycleCheck()
{
    queue <int> Q;
    for (int i(1); i <= n; i++)
        if (C[i] == 1)
            Cy[i] = 1, Q.push(i);
    while (Q.size())
    {
        int i(Q.front()); Q.pop();
        for (auto& [a, b] : Gr[i])
            if (--C[a] == 1 && !Cy[a])
                Cy[a] = 1, Q.push(a);
    }
}
void LCAInit(int p, int q, int d)
{
    D[p] = d, G[p] = q;
    for (auto& [x, y] : Gr[p])
        if (Cy[x] && !D[x])
        {
            dp[x][0] = p;
            mdp[x][0] = y;
            LCAInit(x, q, d + 1);
        }
}
void SparseTableDP()
{
    for (int j(1); j < 18; j++)
        for (int i(1); i <= n; i++)
        {
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
            mdp[i][j] = min(mdp[i][j - 1], mdp[dp[i][j - 1]][j - 1]);
        }
}
int GetLCA(int x, int y)
{
    if (D[x] < D[y]) swap(x, y);
    int d(D[x] - D[y]), g(1e9);
    for (int i{}; d; d >>= 1, i++)
        if (d & 1)
            g = min(g, mdp[x][i]), x = dp[x][i];
    if (x ^ y)
    {
        for (int i(17); !!~i; i--)
            if (dp[x][i] ^ dp[y][i])
            {
                g = min({ g, mdp[x][i], mdp[y][i] });
                x = dp[x][i]; y = dp[y][i];
            }
        g = min({ g, mdp[x][0], mdp[y][0] });
    }
    return g;
}
void CycleNumbering(int p, int q)
{
    for (auto& [x, y] : Gr[p])
        if (!Cy[x] && !rev[x] && x ^ q)
        {
            rev[x] = ++k;
            arr.push_back(y);
            CycleNumbering(x, p);
        }
}
int SegUpdate(int n, int s, int e, int p, int q)
{
    if (s > p || e < p) return seg[n];
    if (s == e) return seg[n] = q;
    int m(s + e >> 1);
    return seg[n] = min(SegUpdate(n << 1, s, m, p, q), SegUpdate(n << 1 | 1, m + 1, e, p, q));
}
int SegQuery(int n, int s, int e, int p, int q)
{
    if (s > q || e < p) return 1e9;
    if (s >= p && e <= q) return seg[n];
    int m(s + e >> 1);
    return min(SegQuery(n << 1, s, m, p, q), SegQuery(n << 1 | 1, m + 1, e, p, q));
}
void Solve(int st = 0)
{
    for (int i(1); i <= n; i++)
        if (!Cy[i])
            st = i, LCAInit(i, i, 1);
    SparseTableDP();
    CycleNumbering(st, st);
    for (int i(1); i <= k; i++) SegUpdate(1, 1, k, i, arr[i]);
    for (int i, j; q--;)
    {
        cin >> i >> j;
        if (G[i] == G[j]) cout << GetLCA(i, j) << '\n';
        else
        {
            int g1 = G[i], g2 = G[j];
            if (rev[g1] > rev[g2]) swap(g1, g2), swap(i, j);
 
            int t1(SegQuery(1, 1, k, rev[g1] + 1, rev[g2]));
            int t2(min(SegQuery(1, 1, k, 1, rev[g1]), SegQuery(1, 1, k, rev[g2] + 1, k)));
            int t3(min(GetLCA(i, g1), GetLCA(j, g2)));
 
            if (i == G[i] && j == G[j]) cout << t1 + t2 << '\n';
            else cout << (t3 <= t1 + t2 ? t3 : t1 + t2) << '\n';
        }
    }
}
int main()
{
    Init();
    CycleCheck();
    Solve();
}

comment

첨에 $TLE$를 좀 얻어 맞아서 좀 당황했다.
아무리 봐도 시간 초과가 날만한 로직이 없었는데..

이유는 그냥 세그 범위를 잘못 줬었다.