트리에서 사용하는 분할정복 기법을 Centroid Decomposition이라고 한다.트리에 존재하는 모든 경로에 대해서 어떤 연산을 수행하려 할때트리를 분할에 서브 트리에 대해 연산을 수행하고, 그러한 서브트리를 merge해 전체 트리에서의 결과값을 얻어 낼 수 있다. 여기서 중요한 것은 주어진 트리르 어떻게 쪼개는지 이다.쪼개는 방법에 따라 시간복잡도가 달라지는데, 분할정복 처럼 트리의 크기를 계속해서 반 씩 쪼깨고 각 서브트리를 처음 트리사이즈 시간만에 merge 할 수 있다면 시간복잡도는 마스터 정리에 의해 O(N lg N)이 된다. 이 문제를 푸는 데 있어 중요한 것은1. Subtree 로 분할할 cutting edge를 어떻게 잡을것인가? 2. 서로다른 Subtree들의 결과값을 어떻게 리니어..
우선 K=1일때에는 트리의 지름에 설치하는것이 가장최적이라는 결론을 내릴수 있는데 그에 대한 증명을 위해서 지름길을 설치했을때의 경로길이를 수식으로 표현해보자 일단 지름길을 설치하지 않았을때에는 모든간선을 2번씩 지나야함으로 경로이길이는 2(N-1)이 된다. 지름길을 하나 설치하면 트리에 간선을 하나 추가하는 행위임으로 반드시 하나의 사이클이 생기게된다.이때 사이클 위에 존재하는 간선은 한번씩만 사이클위에 속하지 않는 간선은 2번씩지나야함으로경로의 길이는 2(N-1) - L + 1이 되는데 L은 (사이클 위에 포함된 정점의 갯수-1)개 이다. 따라서 K=1일때는 간선을 추가하여 만드는 사이클의 길이(즉, 정점갯수-1) 가 최대가 되게 하면 됨으로 트리에 지름에 설치하는것이 가장 최적이라는 결과가 나온다...