BOJ)8012 한동이는 영업사원!

문제:icpc.me/8012

한동이가 방문해야 할 도시를 x->y->z->w 순이라면 

x->y의 거리와 y->z의 거리 z->w의 최소시간을 더해서 출력하는게 답이된다.

결국 N,M제한 때문에 거리를 logN의 시간복잡도에 해결을 해줘야하는데 

우리는 주어진 그래프가 트리라는걸 이용하여 LCA를 통하여 계산해 줄수 있다.

x와 y의 최단 거리는 결국 모든 간선의 가중치가 1이니까 깊이를 이용하여 dph[x]+dph[y]-2*dph[lca(x,y)] 로 계산할 수 있다.

이를 이용하여 답을 구해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 30000
using namespace std;
int n, m, visited[MAX_N + 1], dph[MAX_N + 1], par[MAX_N + 1][20], x, y, r;
vector<vector<int>>vt;
void dfs(int v, int d) {
    visited[v] = true;
    dph[v] = d;
    for (auto next : vt[v]) {
        if (visited[next])
            continue;
        par[next][0] = v;
        dfs(next, d + 1);
    }
}
void f() {
    for (int j = 1; j < 20; j++) {
        for (int i = 1; i <= n; i++)
            par[i][j] = par[par[i][j - 1]][j - 1];
    }
}
int lca(int x, int y) {
    if (dph[x] > dph[y])
        swap(x, y);
    for (int i = 19; i >= 0; i--) {
        if (dph[y] - dph[x] >= (1 << i))
            y = par[y][i];
    }
    if (x == y)return x;
    for (int i = 19; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}
int main(){
    scanf("%d", &n);
    vt.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d", &x, &y);
        vt[x].push_back(y);
        vt[y].push_back(x);
    }
    dfs(1, 0);
    f();
    y = 1;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &x);
        int qlca = lca(x, y);
        r += dph[x] + dph[y] - 2 * dph[qlca];
        y = x;
    }
    printf("%d\n", r);
    return 0;
}