Optimal node ranking of a tree.

rank_tree.cpp

// int rank[N]; vector<int> G[N];
auto rank_tree(int i, int p=-1) {
	int x=0, y=0;
	for(int j:G[i]) if(j!=p) {
		auto z=rank_tree(j, i);
		y|=x&z, x|=z;
	}
	x=(x|(1<<31-__builtin_clz(y<<1|1))-1)+1;
	rank[i]=__builtin_ctz(x);
	return x;
}

트리에서 동일한 rank를 가진 두 노드 u, v가 있을 때, u-v 경로에는 더 큰 rank를 가진 노드가 반드시 존재한다.

• 이에 대한 설명은 Optimal Search On Tree에 간략히 되어 있다. 여기선 이 알고리즘을 구현하는 방법에 대해 설명한다.

용어:

• 노드 u의 자손 노드 v에 대해, u-v 경로에 v의 rank보다 더 큰 rank를 가진 노드가 없다면 u는 v가 '보인다'고 하자.
• 또한 u에서 보이는 노드 v의 rank가 r이라 하면, u는 r도 '보인다'고 하자.

알고리즘:

• 아직 rank가 매겨지지 않은 노드 i가 있을 때, i에서 보이는 노드 u와 v의 rank가 같다고 하자.
• 이 경우 위에 적어둔 rank의 정의에 따라서, 반드시 i의 rank가 u와 v보다 크도록 해야 함은 자명하다.
• i의 부모 노드 p에선 i에서 보이던 노드 중 i보다 rank가 작은 노드들이 보이지 않게 된다. 물론 보이지 않게 되는 노드엔 u와 v가 포함된다.

구현:

• x는 i에서 보이는 rank의 집합을 비트로 나타낸 것이고, y는 i에서 두 개 이상 보이는 rank의 집합이다.
  • rank는 floor(lg(N)) 이하이므로, 일반적인 상황에서는 int 자료형으로 충분히 나타낼 수 있다.
• x+1을 하면 꺼진 비트 중 가장 작은 게 켜지고, 그보다 작은 켜진 비트들은 모두 꺼진다. 즉, 보이지 않는(사용하지 않은) rank 중 가장 작은 것을 골라 i에 부여한다.
  • 예: 01001011 → 01001100
• 그런데, i에 붙여지는 rank는 y의 최대 rank보다 커야 한다. 다른 말로 하면, y의 최대 rank 이하인 rank들은 사용할 수 없다.
• 사용할 수 없는 rank의 집합은 (1<<31-__builtin_clz(y<<1|1))-1으로 구할 수 있고, 이를 x와 OR 연산한 뒤 +1을 해주면 i에 rank를 부여한 뒤의 x를 구할 수 있다.
  • __builtin_clz는 입력으로 들어온 수가 0이면 UB이기 때문에, 위 코드를 (1<<32-__builtin_clz(y))-1로 대체할 수는 없다.
• 이 때, i에 부여된 rank는 __builtin_ctz(x)이고, 최대 rank(혹은 깊이)는 31-__builtin_clz(x)이다.