트리의 노드 순서 정리해서 구간으로 만들기

제목 그대로, 트리의 노드 순서를 다시 정리하여 구간으로 표현하는 것이다.

그림으로 보면, 트리의 구조와 왼쪽과 같았다면, 각 트리의 번호를 오른쪽처럼 변경하는 것이다.

순서는 전위순회(pre-order)로 탐색하면서 번호를 붙이면 된다.

이게 왜 필요할까?

제목에서 이미 말한거지만, 구간으로 표현하는 것이 더 용이할 때 사용한다.

특히 트리를 세그먼트 트리나 펜윅 트리 등의 구간합/부분합으로 변형하여 문제 해결이 필요한 경우이다.

노드의 번호를 위처럼 정리하면, 각 노드가 포괄하는 노드는 항상 확실하다.

"자신의 번호 + 그 노드의 서브 트리(들)의 크기"가 포함할 수 있는 자식의 마지막 번호와 같다.

그럼 트리를 일렬로 펴서 다룰 수 있다.

코드

	#define MAX_V 100001
	int id = 0;
	int L[MAX_V], R[MAX_V]; // [L, R]
	vector<int> adj[MAX_V];
	int dfs(int cur) {
	int i = ++id, cnt = 0;
	L[cur] = i;
	for (auto& nxt : adj[cur]) {
	cnt += 1 + dfs(nxt);
	}
	R[cur] = i + cnt;
	return cnt;
	}

view raw eulerian-path.cpp hosted with ❤ by GitHub

관련 문제 (+스포일러)

• BOJ 2820 - 자동차 공장 : 트리를 일렬로 펴서, 각 서브 트리에 대한 변화량을 세그먼트 트리 + Lazy propagation으로 관리한다.
• BOJ 14268 - 내리 칭찬 2 : 2820번 문제와 매우 유사하다. (업데이트 범위만 살짝 다름)
• 알고스팟 - 족보 탐험 : 트리를 펴서 LCA를 구할 수 있다. 부모 노드(조상)은 항상 번호가 빠르다는 점을 이용하면 된다.
• BOJ 15899 - 트리와 색깔 : 족보 탐험 문제처럼 일렬로 펴는데, 업데이트가 없으므로 k번째 수를 찾는 문제로 쉽게 해결할 수 있다.