190209 BOJ 1761번 정점들의 거리

LCA

처음에는 단순하게 두 정점의 깊이를 맞추고 한 칸씩 올라가면서 

LCA를 확인하는 풀이로 맞았는데 시간이 1초가 넘어갔다.

그래서 어떻게 최적화를 할 지 고민하다가 트리를 그려보니 느낌이 왔다.

정점 7과 2 사이의 거리 =  (1과 7 사이의 거리 + 1과 2 사이의 거리 - 1과 4사이의 거리 * 2)

1. 처음에 깊이를 초기화해주는 동시에 거리값도 따로 저장해둔다.

2. LCA를 구하고 위 식과 같이 계산해준다.

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define endl '\n'
#define ll long long
#define mp(a,b) make_pair(a,b)
#define sws ios::sync_with_stdio(false), cin.tie(NULL)
#define MAX_INT 2000000000
#define pii pair<int, int>
using namespace std;
int N, M, x, y, w;
vector<pii> tree[40002];
queue<int> q;
int depth[40002];
int val[40002];
int D[18][40002];
int main() {
    sws;
    cin >> N;
    FOR(i, 0, N + 1) depth[i] = -1;
    FOR(i, 0, N - 1) {
        cin >> x >> y >> w;
        tree[x].push_back(mp(y, w));
        tree[y].push_back(mp(x, w));
    }
    D[0][1] = 1;
    val[1] = 0;
    depth[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (pii next : tree[now]) {
            int nnode = next.first;
            int cost = next.second;
            if (depth[nnode] == -1) {
                depth[nnode] = depth[now] + 1;
                val[nnode] = val[now] + cost;
                D[0][nnode] = now;
                q.push(nnode);
            }
        }
    }
 
    FOR(k, 1, 18) FOR(n, 1, N + 1) D[k][n] = D[k - 1][D[k - 1][n]];
 
    cin >> M;
    while (M--) {
        cin >> x >> y;
        if (depth[x] > depth[y]) swap(x, y);
        int tempx = x, tempy = y;
        for (int k = 17; k >= 0; k--)
            if (depth[x] <= depth[D[k][y]]) y = D[k][y];
 
        if (x == y) cout << val[tempy] - val[x] << endl;
 
        else {
            for (int k = 17; k >= 0; k--)
                if (D[k][x] != D[k][y])     x = D[k][x], y = D[k][y];
            x = D[0][x], y = D[0][y];
            
            cout << val[tempy] + val[tempx] - val[x] - val[x] << endl;
        }
 
    }
}