백준 24889 - 통행량 조사 (C++)

문제

• 문제 링크

  
   BOJ 24889 - 통행량 조사 
  

• 문제 요약

$N$개의 도시가 $N$개의 간선으로 이루어져 있다.
차량 집단 $Q$개의 통행 정보가 주어질 때, 각 도로마다 지날 가능성이 있는 차량의 수를 계산해보자.
단, 통행에선 각 도시와 도로를 최대 한 번 이용하며 차량 집단이 이용할 가능성이 있는 모든 도로가 고려되어야 한다.


• 제한

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




$3 ≤ N ≤ 200,000$

$1 ≤ Q ≤ 200,000$

$1 ≤ w_i ≤ 5,000$

연결하는 도시 쌍이 동일한 도로가 여러 개 주어지지 않고, 임의의 두 도시는 도로를 통해 서로 이동할 수 있다.

알고리즘 분류

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

풀이

오랜만에 $Unicyclic$ $Graph$ 유형의 문제를 풀었다.

이 문제 나 요 문제 를 풀면서 했던 전처리를 이번 문제에서도 진행해 주었다.

간단히 말하면 주어진 그래프를 $k$개의 정점$(g_1, g_2, ... g_k)$을 루트로 하는 트리로 바라보고, 각 트리 별 $LCA$ 전처리와 그룹화를 진행한다는 것이다.

이때 $g_1, g_2, ... g_k$는 사이클을 형성한다.


쿼리를 보자.

$Unicyclic$ $Graph$ 의 특성에 따라 사이클을 지날 때, 아닐 때로 구분할 수 있다.
내 풀이 방식대로 말한다면 같은 그룹 내에서 이동할 때, 서로 다른 그룹 간 이동할 때로 말할 수 있겠다.

---

먼저 같은 그룹 내 이동($=$ 트리 내 이동)하는 경우를 생각해보자.

경로 상 쿼리를 다루므로 $hld$ 같은 강력한 친구를 끌어와야 하나$?$ 싶지만 조금만 생각해보면 정말 간단하게 업데이트를 적용할 수 있다.

$k$번의 전처리를 할 때, 어떤 루트 $g_i$로부터 시작하여 그 하위 트리로의 탐색을 진행한다.

이 과정에선 $DAG$를 형성할테고, 루트 $g_i$를 제외한 모든 하위 정점들은 자신에게 향하는 간선이 존재한다.

그 간선을 해당 정점과 매칭시키면, 그 간선의 카운트는 해당 정점으로써 기록된다.

이제 $s_i$에서 $e_i$로 $w_i$대의 차량 이동이 발생할 때, 어떤 처리를 해줘야할까?

결론은 $cnt[s_i], cnt[e_i]$에 $+w_i$, $cnt[lca(s_i, e_i)]$에 $-2*w_i$의 값을 기록한다.

왜 이렇게 처리할까$?$

쿼리에서 $w_i$를 더해줘야하는 정점들은, $s_i$에서 $e_i$로 향하는 경로 상의 $LCA(s_i, e_i)$를 제외한 모든 정점들이다.
$LCA(s_i, e_i)$를 왜 제외하는지 모르겠다면, 앞의 과정에서 간선 - 정점 매칭을 어떤식으로 했는지 다시 생각해보고 오자.

결국 위와 같이 쿼리를 처리한 뒤, 각 $g_i$마다 자식 노드들의 $cnt$값을 모두 흡수하는 $DFS$로 모든 업데이트를 적용할 수 있다.

선형 구조에서의 $imos$법을 트리 위에서 비슷하게 진행한다고 이해하면 쉬울 것이다.

---

사이클을 지날 때이다.

사실 앞서 소개한 문제들에선 사이클 위에서도 경로 별 최솟값을 찾는 등의 추가적인 처리가 필요했다.

히지만 이번 문제에선 이용 가능성이 있는 모든 도로를 고려한다고 한다.
즉, 사이클을 지난다는 것 자체만으로 사이클 위의 모든 정점들의 $cnt$가 증가한다.

이는 사이클을 지나는 쿼리가 올 때마다 $w_i$의 값을 누적하는 변수 하나로 쉽게 취합할 수 있다.
$cnt[s_i], cnt[e_i]$에도 $w_i$를 누적하기 때문에, 각 루트에 $w_i$가 두 번 누적되지 않도록 잡아주어야 한다.

이후 최종 $DFS$로 답들을 계산할 때 사이클 위에 있는 정점이라면 변수에 기록된 값을 더해주면 된다.

아, 트리에서와 다르게 사이클 위에서의 간선 - 정점 매칭을 추가로 해줘야 한다.
나같은 경우 어떤 한 시작점을 고정한 채 한 방향으로 돌며 들어오는 간선을 지정해주었다.

---

내가 구현을 조금 복잡하게 한 건가 전체 코드가 좀 긴데, 그냥 위의 내용들을 착실하게 구현한 것이다.
변수, 배열 별 역할을 나열하고 끝내겠다.

$dep[x]$ : 트리 별 루트의 깊이를 $0$이라 할 때, 정점 $x$의 깊이.

$dp[x][y]$ : 정점 $x$의 $2^y$번째 부모 정점.

$cnt[x]$ : 정점 $x$에 매칭된 간선을 지나는 $w_i$를 누적.

$group[x]$ : 정점 $x$가 속한 그룹. 어떤 트리의 루트 $x$에 대해 $group[x] = x$ 로 잡는다.

$rec[x]$ : 정점 $x$에 매칭된 간선.

$ind[x]$ : 정점 별 $indegree$. 처음 사이클 분리에 사용된 후 정점 $x$가 사이클에 속한지 판단하는 용도로 이용.

$cycle$_$st$ : 사이클의 시작 정점.

$ccnt$ : 사이클을 지나는 쿼리의 $w_i$를 누적.

전체 코드

#include<bits/stdc++.h>
#define N 200001
using namespace std;
 
vector <pair<int, int>> Gr[N];
 
int dep[N], dp[N][19], cnt[N];
int group[N], rec[N], ind[N];
 
int n, q, ans[N];
int cycle_st, ccnt;
 
void Input()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int u, v, i(1); i <= n; i++)
    {
        cin >> u >> v;
        Gr[u].emplace_back(v, i);
        Gr[v].emplace_back(u, i);
        ind[u]++, ind[v]++;
    }
}
void FindCycle()
{
    queue <int> Q;
    for (int i(1); i <= n; i++)
        if (!--ind[i])
            Q.push(i);
 
    while (Q.size())
    {
        int now(Q.front()); Q.pop();
        for (auto& [next, edge_n] : Gr[now])
            if (ind[next] && !--ind[next])
                Q.push(next);
    }
 
    for (int i(1); i <= n; i++)
        if (ind[i])
        {
            if (!cycle_st) cycle_st = i;
            group[i] = i;
        }
}
void CycleRec(int now, int prev)
{
    for (auto& [next, edge_n] : Gr[now])
        if (next ^ prev && ind[next] && !rec[next])
        {
            rec[next] = edge_n;
            CycleRec(next, now);
        }
}
void LCAdfs(int now, int g_n)
{
    group[now] = g_n;
    for (auto& [next, edge_n] : Gr[now])
        if (!group[next])
        {
            dep[next] = dep[now] + 1;
            dp[next][0] = now;
            rec[next] = edge_n;
 
            LCAdfs(next, g_n);
        }
}
void TableDP()
{
    for (int j(1); j < 19; j++)
        for (int i(1); i <= n; i++)
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
int getLCA(int u, int v)
{
    int diff(dep[u] - dep[v]);
 
    for (int i{}; diff; diff >>= 1, i++)
        if (diff & 1)
            u = dp[u][i];
    if (u ^ v)
    {
        for (int i(18); !!~i; i--)
            if (dp[u][i] ^ dp[v][i])
                u = dp[u][i], v = dp[v][i];
        u = dp[u][0];
    }
    return u;
}
void LCAInit()
{
    for (int i(1); i <= n; i++)
        if (ind[i])
            LCAdfs(i, group[i]);
    TableDP();
}
void Query()
{
    while (q--)
    {
        int s, e, w; cin >> s >> e >> w;
        if (dep[s] < dep[e]) swap(s, e);
 
        cnt[s] += w, cnt[e] += w;
 
        if (group[s] == group[e])
            cnt[getLCA(s, e)] -= w << 1;
        else
        {
            ccnt += w;
 
            cnt[group[s]] -= w;
            cnt[group[e]] -= w;
        }
    }
}
void Sweeping(int now, int prev)
{
    for (auto& [next, edge_n] : Gr[now])
        if (next ^ prev && !ind[next])
        {
            Sweeping(next, now);
            cnt[now] += cnt[next];
        }
    ans[rec[now]] += cnt[now];
    if (ind[now]) ans[rec[now]] += ccnt;
}
void End()
{
    for (int i(1); i <= n; i++)
        if (ind[i])
            Sweeping(i, i);
    for (int i(1); i <= n; cout << ans[i++] << '\n');
}
int main()
{
    Input();
    FindCycle();
    CycleRec(cycle_st, 0);
    LCAInit();
    Query();
    End();
}

comment

$Unicyclic$ $Graph$ 유형 문제 제보 받습니다.