Rerooting Technique (1) 썸네일형 리스트형 Rerooting Technique on Tree 이 게시글에서는 트리에서 할 수 있는 rerooting technique라는 것을 다뤄본다. Rerooting? 자연수 N개의 노드로 구성되고 루트가 정해진 트리가 주어져 있고 배열에 다음과 같은 정보가 담기길 원한다고 해보자. sub[i] = i번째 노드가 루트인 서브 트리에 대해 해당 트리에 속한 노드의 개수 이 배열을 완성하기 위해서 어떻게 해야 할까? 먼저 생각나는 단순한 방법으로는 각 노드마다 dfs를 돌아 노드의 개수를 세는 $O(N^{2})$ 방법을 떠올릴 수 있다. 하지만 당연하게도 이런 글을 쓴다는 것은 $O(N^{2})$ 시간 복잡도로 해결할 수 없도록 N의 크기가 $10^{5}$ 이상인 경우에 대해 푸는 방법을 알아보는 것이므로 위 방법은 쓸 수 없다. 게다가 각 노드가 루트라고 할 .. 이전 1 다음
