트리에서의 Sqrt Decomposition

1) 트리에서 branch를 나눔

2) branch를 나누는 기준은 현재 정점에서 자식 노드들이 여럿일 때, 첫 번째 branch는 부모와 x를 잇는 branch와 같다고 하고, 나머지들은 각각 새로운 branch.

3) 현재 branch의 길이가 이상이면 cut.

그림으로 표현하면 대충 이런 식이 된다.

dfs numbering하면서 branch를 나누는 코드는 아래와 같다.

cn : branch number, bc : branch에 포함된 노드의 개수, col[x] : x 노드의 branch index

y라는 노드에서 x라는 노드로 올라가면서 일련의 작업을 하는 코드는 아래와 같다.

붉은색 부분에는 branch 전반에 대한 작업, 푸른색 부분에는 특정 노드에 대한 작업을 해주면 된다. 이 코드는 노드와 부모 노드 사이에 대한 간선에 대한 작업을 하느라 노드 x에 대한 작업은 해주지 못한 점을 주의해서 보면 되겠다.

위 코드들은 2016 Spring RUN@KAIST Programming Contest E2번 Traffic (Large)를 풀었던 코드의 일부이다.