LCA ( Least Common Ancestor )

LCA 첫번째 방법 ( 구간 트리 + 전위순회 )

백준 11437, 11438

각 정점을 전위순회할 때 거치는 모든 노드의 번호의 순서(자신으로 돌아올 때도 자기 자신을 넣는다 )를 trip 배열에 저장하고 그 trip 배열을 최소 구간 트리로 구현한다.

두 정점이 처음으로 등장하는 두 구간에서 순서가 가장 빠른 정점이 최소 공통 조상이 된다. ( 전위순회는 항상 부모가 자식보다 먼저 나오기 때문에 더 빠른 번호가 부모이다. )

번호, 순서를 매핑하는 배열과 노드가 처음으로 등장하는 trip의 index를 저장한 배열이 필요하다.

아 그리고 입력이 어떤 정점이 부모인지를 모르기 때문에 두개 다 연결시켜놓고 dfs를 돌리면서 트리 형태를 만들어 주었다.

 

다른 알고리즘이 있던데 그 걸 확인해 봐야겠다.

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

struct RMQ {

	vector<int> rangeMin;
	int n;

	RMQ(vector<int>& arr) {
		n = arr.size();
		rangeMin.resize(n * 4);
		init(arr, 1, 0, n - 1);
	}

	int init(vector<int>& arr, int node, int left, int right) {

		if (left == right) {
			return rangeMin[node] = arr[left];
		}

		int mid = (left + right) / 2;
		return rangeMin[node] = min(init(arr, node * 2, left, mid), init(arr, node * 2 + 1, mid + 1, right));
	}

	int query(int left, int right, int nLeft, int nRight, int node) {
		if (left > nRight || right < nLeft) {
			return 9999999;
		}

		if (nLeft >= left && right >= nRight) {
			return rangeMin[node];
		}

		int mid = (nLeft + nRight) / 2;

		return min(query(left, right, nLeft, mid,node * 2), query(left, right, mid + 1, nRight,node*2+1));
	}

	int query(int left, int right) {
		return query(left, right, 0, n - 1, 1);
	}

};

const int MAX_N = 100001;

vector<vector<int>> child(MAX_N + 1);
vector<int> noToSerial(MAX_N + 1);
vector<int> serialToNo(MAX_N + 1);
vector<int> locTrip(MAX_N + 1);
vector<int> depth(MAX_N + 1);

int serial;

void traverse(int here, int d, vector<int>& trip) {

	noToSerial[here] = serial;
	serialToNo[serial] = here;
	serial++;

	depth[here] = d;

	locTrip[here] = trip.size();
	trip.push_back(noToSerial[here]);

	for (int i = 0; i < child[here].size(); i++) {
		traverse(child[here][i], d + 1, trip);
		trip.push_back(noToSerial[here]);
	}
}

int lca(RMQ& rmq, int u, int v) {
	int lu = locTrip[u];
	int lv = locTrip[v];

	if (lu > lv) {
		swap(lu, lv);
	}

	return serialToNo[rmq.query(lu, lv)];
}

vector<vector<int>> graph(MAX_N+1);
vector<int> visit(MAX_N+1,0);

void makeTree(int idx) {
	visit[idx] = true;

	for (int i = 0; i < graph[idx].size();i++) {
		if (visit[graph[idx][i]] == true) {
			continue;
		}
		child[idx].push_back(graph[idx][i]);
		makeTree(graph[idx][i]);
	}
}


int main() {
	int n;

	scanf("%d", &n);

	int p, c;

	for (int i = 0; i < n - 1; i++) {
		scanf("%d%d", &p, &c);
		graph[p].push_back(c);
		graph[c].push_back(p);
	}

	makeTree(1);

	vector<int> trip;

	traverse(1, 0, trip);
	RMQ rmq(trip);

	int m;

	scanf("%d", &m);
	int u, v;
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &u, &v);
		printf("%d\n", lca(rmq,u, v));
	}
}