1761번

1761번 - 정점들의 거리

이 문제 역시 LCA(lowest common ancestor) 를 이용해서 풀 수 있는 문제였다.

일단 간선들을 입력받고, bfs를 통해서 하나의 루트를 정해서 깊이를 체크해준다.

그다음 lca 를 구하는 방법대로 , 첫번째로 높이를 맞추고, 두번째로 높이가 맞으면 두 노드가 같아질 때 까지 반복한다.

이 때, 높이를 맞추고, 같아질 때까지 반복할때마다 간선의 가중치를 더해주면 답을 구할 수 있다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int p[40001];
int h[40001];
bool check[40001];
vector<vector<pair<int, int>>> v(40001);
void bfs(int start)
{
    p[start] = start;
    h[start] = 1;
    check[start] = true;
    
    queue<int> q;
    q.push(start);
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i].first;
            int w = v[now][i].second;
 
            if (!check[next])
            {
                p[next] = now;
                h[next] = h[now] + 1;
                check[next] = true;
                q.push(next);
            }
        }
    }
}
int LCA(int a, int b,int sum)
{
    while (h[a] != h[b])
    {
        if (h[a] > h[b])
        {
            for (int i = 0; i < v[a].size(); i++)
            {
                if (v[a][i].first == p[a])
                {
                    sum += v[a][i].second;
                    break;
                }
            }
 
            a = p[a];
        }
        else
        {
            for (int i = 0; i < v[b].size(); i++)
            {
                if (v[b][i].first == p[b])
                {
                    sum += v[b][i].second;
                    break;
                }
            }
 
            b = p[b];
        }
    }
 
 
    while (a != b)
    {
        for (int i = 0; i < v[a].size(); i++)
        {
            if (v[a][i].first == p[a])
            {
                sum += v[a][i].second;
                break;
            }
        }
        for (int i = 0; i < v[b].size(); i++)
        {
            if (v[b][i].first == p[b])
            {
                sum += v[b][i].second;
                break;
            }
        }
 
        a = p[a];
        b = p[b];
    }
 
    return sum;
}
int main()
{
    int n, m;
    scanf("%d", &n);
    vector<int> ans;
 
 
    for (int i = 1; i < n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
    }
 
    bfs(1);
 
    scanf("%d", &m);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        ans.push_back(LCA(a, b,0));
    }
 
    for (int i = 0; i < ans.size(); i++)
    {
        printf("%d\n", ans[i]);
    }
 
    return 0;
}