계통 트리 (KOI 2008)

http://59.23.113.171/pool/koi_tree/koi_tree.php?pname=koi_tree

Observation 1.

문제를 쉽게 해서 유사도가 2일 때를 가정해보자. 그 때는

 - 부모가 같으면 연결되어 있다.  - 부모가 다르면 연결이 안되어 있다.

고로 완전 그래프인 컴포넌트들이 떠다니는 그래프를 상상할 수 있다.

부모가 같은 게 뭔가 중요해 보인다는 사실을 알 수 있고, 난 여기서 착안해서 계통 트리를 다음과 같이 재정의했다. 

 * 계통 트리는 S+1개의 노드로 이루어진 트리로, 각각의 노드는 1 ~ N의 개체들을 0개 이상 포함하고 있다. 이 때, 모든 개체는 정확히 한개의 노드에 속한다.

말로 하기가 너무 뭐한데.. 저 말대로 예제를 그려보면 대충 이런 느낌의 트리가 나온다. 이렇게 해서라도 이해가 됐으면..

이제 이렇게 되면 유사도를 훨씬 더 쉽게 정의할 수 있다. 유사도 X -> (트리 상에서 두 개체의 거리) + 2 이다. 고로, 유사도 2는 두 개체가 같은 노드에 있는 거고, 유사도 3은 두 개체가 인접한 노드에 있는 거다.

Observation 2.

두 개체가 같은 노드에 속하면, 인접한 개체들의 집합이 똑같다. 이 아이디어를 통해서 정렬 한번에 같은 노드였는지 다른 노드였는지를 알 수 있다.

같은 노드인지 다른 노드인지를 쉽게 알 수 있으니, 주어진 정보가 유사도 2의 정보인지 3의 정보인지를 알 수 있고, 유사도 3의 정보였다면 이제 두 개체가 속한 노드 간에 간선을 이어주면 된다. 이렇게 계통 트리의 모든 정보가 완성되었으니 걍 찍어주면 된다.

정렬에 대해서 조금 더 고찰 (?) 을 해보자면, 그냥 주어진 그래프를 vector에 담아서 정렬을 하면 N^2lgN이다. MlgM을 증명할 수도 있을법 하긴 한데 난 아직 잘 모르겠고... 고로 해싱 / bitset 등의 방법을 사용해서 빠르게 정렬해주는 것이 좋아보인다. 사실 suffix array 쓰면 O(N + M)에도 해결 가능하긴 함 ㅋㅋ