백준 8012번: 한동이는 영업사원! (C++)

https://www.acmicpc.net/problem/8012

8012번: 한동이는 영업사원!

---

Solved By: LCA

 

Floyd-Warshall 같은 최단 경로 알고리즘이 떠오르기도 하지만 시간 복잡도가 O(N^3)인 걸 생각하면 다른 방법을 떠올려야 합니다.

 

문제를 읽어보면, '사이클이 없다', 'edge가 n - 1개다.', 'Undirected다.'이런 것을 보면 트리가 떠오릅니다. 그리고, 무조건 1번 노드에서 시작하니 1을 Root Node로 둔 트리입니다.

 

경로 값이 전부 1이기도 하고, 간단하게 LCA로 풀 수 있습니다.

 

쿼리를 읽어보면 시작점 -> 도착점으로 다음 쿼리에서는 도착점이 시작점이 됩니다.

이를 인지하고, 쿼리를 처리하면 됩니다.

 

#include <iostream>
#include <vector>
#define MAX 30001
using namespace std;

int n;
vector<int> adj[MAX];
int level[MAX];
int parent[MAX];

void dfs(int now, int par){
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(next == par) continue;
        level[next] = level[now] + 1;
        parent[next] = now;
        dfs(next, now);
    }
    return;
}

void swap(int *a, int *b){
    int *temp = a;
    a = b;
    b = temp;
}

int lca(int a, int b){
    int ret = 0;
    if(level[a] < level[b]) swap(a, b);
    
    int diff = level[a] - level[b];
    ret += diff;
    
    while(level[a] != level[b]){
        a = parent[a];
    }
    
    int cnt = 0;
    while(a != b){
        a = parent[a];
        b = parent[b];
        cnt++;
    }
    
    ret += cnt * 2;
    
    return ret;
}

int main(){
    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    level[1] = 0;
    dfs(1, 0);
    
    int m; cin >> m;
    vector<int> query;
    for(int i = 0; i < m; i++){
        int q; cin >> q; query.push_back(q);
    }
    
    int res = 0;
    for(int i = 0; i < query.size() - 1; i++){
        res += lca(query[i], query[i + 1]);
    }
    
    cout << res;
    return 0;
}