Boj 3584) Lca

Nearest Common Ancester

백준 3584

설명

LCA 는 트리 구성 이후의 작업이 O(LogN) 임.

그런데 이건 한번만 찾으면 되므로 트리구성이 필요가 없음.

그래서 간단하게 set 을 이용해 한쪽의 조상목록을 넣고, 다른쪽의 부모 중 가장 깊은 노드를 들고오게 함.

시간 복잡도

O(N)

코드

int lines[50001];

int main()
{
	fastio;
	int t;
	cin >> t;
	while (t--)
	{
		int n, tmp1, tmp2;
		cin >> n;
		fill(lines, lines + n + 1, 0);
		for (int i = 0; i < n - 1; i++)
		{
			cin >> tmp1 >> tmp2;
			lines[tmp2] = tmp1;
		}

		cin >> tmp1 >> tmp2;
		set<int> parents;
		while (tmp1)
		{
			parents.insert(tmp1);
			tmp1 = lines[tmp1];
		}
		while (parents.find(tmp2) == parents.end())
			tmp2 = lines[tmp2];
		cout << tmp2 << '\n';
	}
}