BOJ)1761 정점들의 거리

문제:icpc.me/1761

두 정점간의 최단거리를 매 쿼리마다 출력하는 문제이다.

우리가 기본적으로 알고 있는 그래프의 최단거리 알고리즘들은 시간복잡도 때문에 사용할 수가 없다.

하지만 우리는 이 그래프가 트리라는것을 이용하여 매 쿼리를 O(logN) 시간마다 처리해 줄 수있다.

우리는 lca를 이용하여 두 노드의 최단 거리를 계산할 것이다.

lca전처리를 위해 dfs를 돌려줄 때 루트에서 부터 자기 자신까지의 거리를 dist배열에 저장해두면

두 노드의 X,Y 의최단 거리는 dist[X]+dist[Y]-2*dist[lca(X,Y)]로 정의 할 수있다.

이를 이용하여 매 쿼리를 logN시간에 처리해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 40000
using namespace std;
int n, m, visited[MAX_N + 1], dph[MAX_N + 1], par[MAX_N + 1][20], dist[MAX_N + 1], x, y, z;
vector<vector<pair<int, int>>>vt;
void dfs(int v, int dh, int dis) {
    visited[v] = true;
    dph[v] = dh;
    dist[v] = dis;
    for (auto u : vt[v]) {
        if (visited[u.first])
            continue;
        dfs(u.first, dh + 1, dis + u.second);
        par[u.first][0] = v;
    }
}
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%d", &x, &y, &z);
        vt[x].push_back({ y,z });
        vt[y].push_back({ x,z });
    }
    dfs(1, 0, 0);
    f();
    scanf("%d", &m);
    while (m--) {
        scanf("%d%d", &x, &y);
        int qlca = lca(x, y);
        printf("%d\n", dist[x] + dist[y] - 2 * dist[qlca]);
    }
    return 0;
}