백준 1761번 (정점들의 거리) c++

문제

1761번: 정점들의 거리

LCA알고리즘을 활용하는 문제입니다.

N개의 노드 트리가 주어지면 연결된 노드에는 거리가 주어집니다.

이때 임의의 두 노드 사이의 거리를 구하면 됩니다.

 

1번 노드를 전체 트리의 루트 노드로 보고 

value[x] 배열을 선언합니다. 

value[x] = 1번 노드부터 x번 노드까지의 거리 합입니다.

따라서 우리는 두 노드를 a, b라 할때 정답은

value[a] + value[b] - 2*value[lca(a, b)] 입니다.

예를 들어 5번 노드와 4번 노드의 거리 합을 구하고 

싶다면 

value[4] = A + D

value[5] = C + A

value[lca(4, 5)] = A

=> value[4] + value[5] - 2*value[lca(4, 5)]

= A + D + C + A -2*A

=> D + C

 

 

 

 

 

---

cin >> n;
	for (int i = 0; i < n - 1; i++) {
		cin >> a >> b>>c;
		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}

기본적인 LCA 알고리즘과 매우 유사합니다. 다른점은 두 노드 간의 거리가 추가 되었다는 점입니다.

vector<pair<int, int>>v[] 를 선언합니다. v[x] = {y, n} x번 노드와 y번 노드가 연결되있고 거리가 n입니다.

---

void dfs(int x, int par) {
	depth[x] = depth[par] + 1;
		for (auto nxt : v[x]) {
			if (nxt.first == par)continue;
			parent[nxt.first][0] = x;
			value[nxt.first] = nxt.second+value[x];//check
			dfs(nxt.first, x);
		}
}

dfs도 똑같습니다. 두 노드간의 깊이를 구해줍니다.

다른점은 //check 표시한 구간 입니다. value[] 함수를 만들어주는 코드입니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n, m, parent[100001][21], depth[100001],value[100001], a, b,c;
vector<pair<int,int>>v[100001];
void dfs(int x, int par);
int lca(int x, int y);
int cnt;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b>>c;
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
    }
    dfs(1, 0);
 
    for (int i = 1; i < 21; i++) {
        for (int j = 1; j <= n; j++) {
            parent[j][i] = parent[parent[j][i - 1]][i - 1];
        }
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        cout << (value[a]+value[b])-2*value[lca(a, b)] << '\n';
    }
    return 0;
}
void dfs(int x, int par) {
    depth[x] = depth[par] + 1;
        for (auto nxt : v[x]) {
            if (nxt.first == par)continue;
            parent[nxt.first][0] = x;
            value[nxt.first] = nxt.second+value[x];//check
            dfs(nxt.first, x);
        }
}
int lca(int x, int y) {
    if (depth[x] > depth[y])swap(x, y);//항상 y의 깊이가 더 깊게 만들자
    for (int i = 20; i >= 0; i--) //y를 x의 깊이만큼 올려주는 작업
        if (depth[y] - depth[x] >= (1 << i)) {
            y = parent[y][i];
        }
    if (x == y)return x; //둘이 같은 노드 일때
    for (int i = 20; i >= 0; i--) {
        if (parent[x][i] != parent[y][i]) {
            x = parent[x][i];
            y = parent[y][i];
        }
    }
    return parent[x][0]; //parent[y][0] 으로 해도된다
}