[백준/BOJ] 백준 1761번 : 정점들의 거리

https://www.acmicpc.net/problem/1761

1761번: 정점들의 거리

LCA(최소 공통 조상)을 구하는 방법으로 최소 공통 조상을 구하고, 트리의 루트로부터 거리 차이를 이용하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits>
using namespace std;

int n;
int m;
vector<pair<int, int>> adj[40001]; //(거리, 정점)
vector<int> maked(40001, 0);
vector<int> cost(40001); //트리의 루트로 부터 거리

//LCA(최소 공통 조상) 해결 방법 이용
vector<int> visited;
vector<int> node_num_to_travel_num(40001, 0); //[정점 번호] = 순환 번호
vector<int> travel_num_to_node_num(40001, 0); //[순환 번호] = 정점 번호
vector<int> node_first_find(40001, 0); //[정점 번호] = 순환에 몇번째에 처음 해당 정점을 만났는지 
int travel_cnt = 0;
vector<int> sgmtt;

vector<int> output;

struct node {
	int number;
	vector<node*> children;
};

node* MakeTree(int here, int add_cost)
{
	node* ret = new node();
	ret->number = here;

	maked[here] = 1;
	cost[here] = add_cost;

	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i].second;
		int this_cost = adj[here][i].first;

		if (maked[there] == 0)
		{
			ret->children.push_back(MakeTree(there, add_cost + this_cost));
		}
	}

	return ret;
}

//트리를 순환하며 번호를 매긴다
void Travel(node* here)
{
	int here_num = here->number;

	travel_cnt++;
	int here_travel_cnt = travel_cnt;

	node_num_to_travel_num[here_num] = here_travel_cnt;
	travel_num_to_node_num[here_travel_cnt] = here_num;
	visited.push_back(here_travel_cnt);
	node_first_find[here_num] = visited.size() - 1;

	for (int i = 0; i < (here->children).size(); i++)
	{
		node* there = (here->children)[i];

		Travel(there);

		visited.push_back(here_travel_cnt); //there을 탐색하고 다시 here 돌아온것
	}
}

int MakeSgmtt(int here, int range_left, int range_right)
{
	if (range_left == range_right)
	{
		return sgmtt[here] = visited[range_left];
	}

	int mid = (range_left + range_right) / 2;
	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return sgmtt[here] = min(MakeSgmtt(left_child, range_left, mid), MakeSgmtt(right_child, mid + 1, range_right));
}

int Query(int here, int range_left, int range_right, int find_left, int find_right)
{
	if (find_right < range_left || range_right < find_left)
		return numeric_limits<int>::max();

	if (find_left <= range_left && range_right <= find_right)
		return sgmtt[here];

	int mid = (range_left + range_right) / 2;
	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return min(Query(left_child, range_left, mid, find_left, find_right), Query(right_child, mid + 1, range_right, find_left, find_right));
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n - 1; i++)
	{
		int u, v, cost;

		cin >> u >> v >> cost;

		adj[u].push_back(make_pair(cost, v));
		adj[v].push_back(make_pair(cost, u));
	}

	node* root = MakeTree(1, 0); //1번 노드가 루트인 트리를 만든다

	Travel(root);
	sgmtt.resize(visited.size() * 4);

	MakeSgmtt(0, 0, visited.size() - 1);

	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int u, v;

		cin >> u >> v;

		//세그먼트 트리 쿼리로 최소 콩통 조상의 순환 번호를 구한다
		int lca_travle_num = Query(0, 0, visited.size() - 1, min(node_first_find[u], node_first_find[v]), max(node_first_find[u], node_first_find[v]));

		//최소 공통 조상의 노드 번호
		int lca_node_num = travel_num_to_node_num[lca_travle_num];

		//루트로부터 거리 차이를 이용한다
		int result = (cost[u] - cost[lca_node_num]) + (cost[v] - cost[lca_node_num]);

		output.push_back(result);
	}

	for (int i = 0; i < output.size(); i++)
		cout << output[i] << "\n";

	return 0;
}