트리의 루트를 로 정하고, 자식부터 DP를 계산한다. 는 의 서브트리를 완전히 덮는 최소 경로 수이다. 는 를 한쪽 끝으로 하고 반대쪽 끝의 값이 인 경로 하나를 부모 방향으로 연장할 수 있도록 남겼을 때, 나머지를 덮는 최소 경로 수이다. 이 열린 경로 자체는 세지 않는다.
자식 에 대해 를 정의하고, 라 하자. 존재하지 않는 상태는 후보에서 제외한다. 다음과 같이 계산한다.
또한 를 자식들의 중 최댓값으로 두되, 이면 도 후보에 넣는다. 그러면
이다. 이 값은 음수일 수도 있으므로 그대로 유지한다.
각 를 값 를 키로 하는 맵에 저장한다. 에서는 임시 맵 으로 시작해 자식 맵을 하나씩 합친다. 합치기 전에 공통 키의 두 값의 합으로 를 갱신하고, 합칠 때는 키마다 최댓값만 남긴다. 이 순서를 지켜야 같은 자식의 상태 두 개를 연결하지 않는다. 병합이 끝나면 맵은 를 나타내므로 모든 값에 를 더한다. 공통 덧셈은 별도의 오프셋으로 관리한다.
항상 작은 맵을 큰 맵으로 옮기고 균형 이진 검색 트리를 사용하면, 한 케이스의 시간 복잡도는 , 공간 복잡도는 이다. 정답은 이다.
증명
가 속한 완성된 경로는 자식 방향 간선을 , , 개 사용한다. 각각 만 남기거나, 끝값이 인 열린 경로를 닫거나, 끝값이 같은 두 자식의 열린 경로를 연결한다. 필요한 경로 수는 각각 , , 이므로 의 점화식을 얻는다.
를 열린 경로의 끝으로 남길 때는 자식을 최대 하나만 사용한다. 따라서 이고, 이를 에 대입하면 위 식이 나온다. 모든 경우가 실제 경로 덮개로 만들어지므로 자식부터 계산한 DP는 최적이다.
병합한 맵에서 키마다 최댓값만 남겨도 새 자식과 연결할 최선의 후보를 잃지 않는다. 이미 처리한 자식 두 개의 최적 조합은 에 기록되어 있다.
작은 맵의 크기를 라 하자. 중복으로 절반 이상이 사라지면 병합 비용을 사라지는 항목에 배분한다. 그렇지 않으면 절반 이상이 살아남고 새 맵의 크기가 적어도 이므로, 비용을 그 항목들에 배분한다. 항목이 살아 있는 동안 소속 맵의 크기는 줄지 않으며, 처음 만드는 항목은 정점당 하나이다. 따라서 각 항목이 부담하는 비용은 총 이고 전체 항목 방문 수는 이다.
