[백준/BOJ] 백준 11438번 : LCA 2

www.acmicpc.net/problem/11438

11438번: LCA 2

최소 공통 조상(LCA) 문제 해결방법을 이용하여 방문 구간의 최소 값을 저장하는 세그먼트 트리를 이용해 문제를 해결했다. 트리를 만들고 트리를 순환하면서 해당 노드의 travel_num를 저장하고, travel_num가 나타내는 노드를 저장한다. 그리고 vector<int> visited로 방문하는 순서를 저장한다. 또한 vector<int> node_first_find(100001, 0)에 here노드를 몇번째에 처음 발견하는지 저장한다. 그리고 visited에서 구간의 최소 값을 저장하는 세그먼트 트리를 만들어 세그먼트 트리 쿼리를 통해 문제를 해결했다. 

 

코드

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

int n;
vector<int> adj[100001];
int m;

vector<int> node_maked(100001, 0);

vector<int> visited; //방문하는 순서를 저장
vector<int> travel_num_to_node_num(100001, 0); //travel_num가 나타내는 노드를 저장
vector<int> node_num_to_travel_num(100001, 0); //해당 노드의 travel_num를 저장
vector<int> node_first_find(100001, 0);
int travel_cnt = 1;

vector<int> range_min;

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

node* Maketree(int node_num)
{
	node* ret = new node();

	ret->number = node_num;

	node_maked[node_num] = 1;

	for (int i = 0; i < adj[node_num].size(); i++)
	{
		int there = adj[node_num][i];

		if (node_maked[there] == 0)
		{
			ret->childeren.push_back(Maketree(there));
		}
	}

	return ret;
}

//최소 공통 조상(LCA) 문제 해결방법을 이용한다
void Travel(node* here)
{
	node_num_to_travel_num[here->number] = travel_cnt; //해당 노드의 travel_num를 저장
	travel_num_to_node_num[travel_cnt] = here->number; //travel_num가 나타내는 노드를 저장

	int this_travel_cnt = travel_cnt;

	visited.push_back(travel_cnt); 
	node_first_find[here->number] = visited.size(); //here노드를 몇번째에 처음 발견하는지 저장 

	travel_cnt++;

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

		Travel(there);

		visited.push_back(this_travel_cnt); //한쪽의 자식노드를 순환하고 다시 here을 방문한다
	}
}

//세그먼트 트리 만들기
int Make_range_min(int range_min_num, int range_left, int range_right)
{
	if (range_left == range_right)
	{
		return range_min[range_min_num] = visited[range_left];
	}

	int mid = (range_left + range_right) / 2;
	int left_chlid = range_min_num * 2 + 1;
	int right_child = range_min_num * 2 + 2;

	return range_min[range_min_num] = min(Make_range_min(left_chlid, range_left, mid), Make_range_min(right_child, mid + 1, range_right));
}

//세그먼트 트리 쿼리
int Query(int range_min_num, int range_left, int range_right, int find_left, int find_right)
{
	if (find_right < range_left || range_right < find_left)
		return 987654321;

	if (find_left <= range_left && range_right <= find_right)
		return range_min[range_min_num];

	int mid = (range_left + range_right) / 2;
	int left_chlid = range_min_num * 2 + 1;
	int right_child = range_min_num * 2 + 2;

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

int Solve(int u, int v)
{
	int u_first_find = node_first_find[u];
	int v_first_find = node_first_find[v];
	int left, right;

	if (u_first_find < v_first_find)
	{
		left = u_first_find;
		right = v_first_find;
	}

	else
	{
		left = v_first_find;
		right = u_first_find;
	}

	int result = Query(0, 0, visited.size() - 1, left - 1, right - 1);

	return travel_num_to_node_num[result];
}

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

	cin >> n;

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

		cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	//루트가 1인 트리를 만든다
	node* root = Maketree(1);

	Travel(root);

	range_min.resize(visited.size() * 4); //세크먼트 트리에 사용하는 배열을 넉넉하게 visited.size()*4으로 한다
	Make_range_min(0, 0, visited.size() - 1); //visited에서 구간의 최소 값을 저장하는 세그먼트 트리를 만든다

	cin >> m;

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

		cin >> u >> v;

		cout << Solve(u, v) << "\n";
	}

	return 0;
}