1R/2016 09 20

오늘의 문제

• [1]

참가자

• 박인서

코드

박인서

#include <cstdio>
#include <vector>
int a[50001] = { 0, }, d[50001];
std::vector<std::pair<int, int>> temp;

int find(int x, int y) {
	while (d[x]>d[y]) x = a[x];
	while (d[x]<d[y]) y = a[y];

	while (x != y)
	{
		x = a[x];
		y = a[y];
	}
	return x;
}

int main() {
	int n;
	scanf("%d", &n);
	a[1] = -1, d[1] = 0;
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		if (a[x] == 0 && a[y] == 0)
			temp.push_back(std::pair<int, int>(x, y));
		else if (a[x] == 0) {
			a[x] = y;
			d[x] = d[y] + 1;
		}
		else {
			a[y] = x;
			d[y] = d[x] + 1;
		}
	}

	while (!temp.empty()) {
		for (int i = 0; i < temp.size(); i++) {
			int x = temp[i].first, y = temp[i].second;
			if (a[y] != 0) {
				a[x] = y;
				d[x] = d[y] + 1;
				temp.erase(temp.begin() + i);
				i--;
			}
			else if (a[x] != 0) {
				a[y] = x;
				d[y] = d[x] + 1;
				temp.erase(temp.begin() + i);
				i--;
			}
		}
	}

	int m;
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int t1, t2;
		scanf("%d %d", &t1, &t2);
		printf("%d\n", find(t1, t2));
	}
	return 0;
}

아이디어

박인서

• 일단 자신의 부모와 깊이를 저장을 해야됨.
  • 처음에 부모와 자식을 저장 할 수 없는 선들을 temp에 저장한 뒤 나중에 고려함.
• 그 뒤에 찾기는 일단 depth를 맞춘 뒤 한 단계씩 올라가면서 두 노드의 값을 비교함.