백준 26262 - 트리 더하기 1 (C++)

문제

• 문제 링크

  
   BOJ 26262 - 트리 더하기 1 
  

• 문제 요약

$N$개의 정점과 $N$개의 양방향 간선으로 이루어진 그래프가 주어진다.
순서쌍 $(x_i, y_i)$ 가 $Q$개 주어질 때, 각 쿼리마다 정점 $x_i$와 $y_i$를 잇는 최단 경로의 길이를 구해보자.

• 제한

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




$2 ≤ N ≤ 2 * 10^5$

$1 ≤ Q ≤ 2 * 10^5$

$1 ≤ d_i ≤ 10^9$

$i$ $≠$ $j$ 이고 $(u_i, v_i) = (u_j, v_j)$ 인 중복 간선이 입력으로 주어질 수 있다.

알고리즘 분류

• 그래프 이론(graphs)
• 트리(trees)
• 최소 공통 조상(lowest common ancestor)
• 누적 합(prefix_sum)

풀이

이 글 에서 한 번 언급 했던 그 문제이다.
위 문제처럼 이번 문제 역시 $Unicycle$ $Graph$ 를 다루는 문제다.

위 문제에선 사이클이 반드시 발생 했지만 이번 문제에선 중복 간선 이슈로 인해 사이클까지 갈 필요가 없을 수 있다.
사이클이 발생하지 않았다면 단순 $LCA$ 기본 문제 수준 이므로 그에 대한 설명은 생략하겠다.

---

사이클 분리 후 여기에 속한 정점들을 루트로 하는 $k$개의 트리에 대해 각각의 하위 노드들에 대한 $Grouping$을 진행하자. $(G_1, G_2, ... G_k)$

동시에 $LCA$ 전처리도 함께 해주는 것이 편하다.
그럼 쿼리는 다음과 같이 처리할 수 있다.

순서쌍 $(i, j)$가 같은 그룹$($트리$)$에 속한 경우

$LCA$ 전처리를 통해 쉽게 구할 수 있다.
구체적으로 순서쌍 $(i, j)$가 $G_x$를 루트로 하는 서브 트리에 속할 때, 루트 정점으로부터 떨어진 거리를 각각 $W[i], W[j]$라 한다면

$d = W[i] + W[j] - 2 * W[LCA(i, j)]$

순서쌍 $(i, j)$가 다른 그룹$($트리$)$에 속한 경우

사이클에서 이동하는 방법은 시계 방향으로 가거나, 반시계 방향으로 가거나 둘 중 하나다.
연속 구간의 합을 빠르게 계산해야 하므로 한 방향으로의 누적 합$(pre[])$ 배열을 만든다면, 그 반대 방향의 거리 역시 바로 계산할 수 있다.

구체적으로 순서쌍 $(i, j)$가 각각 그룹 $G_x$, $G_y$에 속한 정점일 때,
사이클 위를 이동할 땐 $min(pre[G_y] - pre[G_x],$ $pre[G_k] - (pre[G_y] - pre[G_x]))$ 의 값을 취한다는 것이다.
이때 인덱스 상 $x < y$ 여야 하며, $pre[G_k]$는 사이클 길이의 총 합이다.

최종적으로 $(i, j)$ 부터 $G_x$, $G_y$의 루트 정점까지 이르는 거리도 고려해 주면

$d = W[i] + W[j] + min(pre[G_y] - pre[G_x],$ $pre[G_k] - (pre[G_y] - pre[G_x]))$

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 200001
using namespace std;
 
vector <pair<int, int>> Gr[N];
int C[N], G[N], Cy[N], D[N], dp[N][19];
ll W[N], pre[N];
ll n, q, cp;
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    map <int, int> M[N];
    cin >> n;
    for (int i, j, w, o{}; o++ < n; M[i][j] = M[i].count(j) ? min(M[i][j], w) : w)
        if (cin >> i >> j >> w; i < j)
            swap(i, j);
    for (ll i(1); i <= n; i++)
        for (auto& [j, w] : M[i])
        {
            Gr[i].emplace_back(j, w);
            Gr[j].emplace_back(i, w);
            C[i]++, C[j]++;
        }
}
void FindCycle()
{
    queue <int> Q;
    for (ll i(1); i <= n; i++)
        if (C[i] == 1)
            Cy[i] = 1, Q.push(i);
    while (Q.size())
    {
        ll t(Q.front()); Q.pop();
        for (auto& [x, y] : Gr[t])
            if (--C[x] == 1 && !Cy[x])
                Cy[x] = 1, Q.push(x);
    }
}
void SubTreeInit(ll p, ll q, ll c, ll d)
{
    G[p] = q; D[p] = d;
    for (auto& [x, y] : Gr[p])
        if (Cy[x] && !G[x])
        {
            W[x] = c + y; dp[x][0] = p;
            SubTreeInit(x, q, W[x], d + 1);
        }
}
void Grouping()
{
    for (ll i(1); i <= n; i++)
        if (!Cy[i])
        {
            SubTreeInit(i, i, 0, 1);
            if (!cp) cp = i;
            D[i] = 0;
        }
}
void CycleInit(ll p, ll q, ll d)
{
    pre[p] = q, D[p] = d;
    for (auto& [x, y] : Gr[p])
    {
        if (x == cp) D[x] = d + 1, pre[cp] = q + y;
        if (!D[x]) CycleInit(x, q + y, d + 1);
    }
}
void SparseTableDP()
{
    for (ll j(1); j < 19; j++)
        for (ll i(1); i <= n; i++)
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
ll GetLCA(ll p, ll q)
{
    if (D[p] < D[q]) swap(p, q);
    for (ll i{}, w(D[p] - D[q]); w; w >>= 1, i++)
        if (w & 1)
            p = dp[p][i];
    if (p ^ q)
    {
        for (ll i(18); !!~i; i--)
            if (dp[p][i] ^ dp[q][i])
                p = dp[p][i], q = dp[q][i];
        p = dp[p][0];
    }
    return p;
}
void Solve()
{
    for (cin >> q; q--;)
    {
        ll i, j; cin >> i >> j;
        ll k(W[i] + W[j]);
        if (G[i] == G[j]) cout << k - 2 * W[GetLCA(i, j)] << '\n';
        else
        {
            ll x(G[i]), y(G[j]);
            if (D[x] < D[y]) swap(x, y);
            ll t(pre[x] - pre[y]);
            cout << k + min(t, pre[cp] - t) << '\n';
        }
    }
}
int main()
{
    Init();
    FindCycle();
    Grouping();
    !cp ? SubTreeInit(1, 1, 0, 1) : CycleInit(cp, 0, 1);
    SparseTableDP();
    Solve();
}

comment

끝