백준 18425 - Putovanje (C++)

문제

• 문제 링크

  
   BOJ 18425 - Putovanje 
  

• 문제 요약

$N$개의 노드로 이루어진 트리와, $N-1$개의 도로에 대한 단일, 복수 패스 비용이 주어진다.
$1, 2, ... , N$번 노드를 차례로 순회할 때, 모든 노드를 순회하는 데 드는 최소 패스 비용을 구해보자.

• 제한

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




$2 ≤ N ≤ 200,000$

$1 ≤ C_1, C_2 ≤ 100,000$

알고리즘 분류

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

풀이

모든 노드를 순회하고난 뒤, 간선마다 사용된 횟수를 알고 있다고 해보자.

그럼 어떤 간선의 단일, 복수 패스 비용 $C1_i, C2_i$에 대해 $min(C1_i * cnt[i], C2_i)$의 값으로 최선의 선택을 해낼 수 있다.

$i - 1$에서 $i$로 갈 때, 매번 일일이 세준다면 $N ≤ 200,000$ 으로 다소 무리가 있다.
아래와같이 추가적인 배열을 정의하자.

$rec[i]$ : $1$에서 $DFS$를 시작할 때, $i$로 들어오는 간선의 번호

$cnt[i]$ : $i$번 간선이 이용되는 횟수

어떤 이동에 대해 $cnt[rec[i - 1]]$과 $cnt[rec[i]]$에 $+1$, $cnt[rec[lca(i - 1, i)]]$에 $-2$의 값을 누적하자.
모든 이동이 끝나고, $1$에서 $DFS$를 다시 돌려보며 자식 노드들의 $cnt$값을 누적해주면 모든 노드에 업데이트를 끝낼 수 있다.

선형 구조에서 $imos$를 쓰는 것과 같은 원리이다.

자세한 건 아래 코드를 참고하자.

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 200001
using namespace std;
 
vector <tuple <int, int>> edge[N];
int dep[N], cnt[N], rec[N], dp[N][18];
int n, C1[N], C2[N];
 
void Input()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i{}, u, v; ++i < n;)
    {
        cin >> u >> v >> C1[i] >> C2[i];
        edge[u].emplace_back(v, i);
        edge[v].emplace_back(u, i);
    }
}
void LCAInit(int now, int depth)
{
    dep[now] = depth;
    for (auto& [nxt, i] : edge[now])
        if (!dep[nxt])
        {
            dp[nxt][0] = now;
            rec[nxt] = i;
            LCAInit(nxt, depth + 1);
        }
}
void TableDP()
{
    for (int j(1); j < 18; j++)
        for (int i(1); i <= n; i++)
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
int getLCA(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, 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(17); !!~i; i--)
            if (dp[u][i] ^ dp[v][i])
                u = dp[u][i], v = dp[v][i];
        u = dp[u][0];
    }
    return u;
}
void Tour()
{
    for (int i(2); i <= n; i++)
    {
        int lca(getLCA(i - 1, i));
        cnt[rec[i - 1]]++, cnt[rec[i]]++;
        cnt[rec[lca]] -= 2;
    }
}
 
ll ans;
void Pre(int now, int prev)
{
    for (auto& [nxt, i] : edge[now])
        if (nxt ^ prev)
        {
            Pre(nxt, now);
            cnt[rec[now]] += cnt[rec[nxt]];
        }
    ans += min((ll)C1[rec[now]] * cnt[rec[now]], (ll)C2[rec[now]]);
}
int main()
{
    Input();
    LCAInit(1, 1);
    TableDP();
    Tour();
    Pre(1, 1);
    cout << ans;
}

comment

끝