각 정점 를 루트로 하는 서브트리에서 떨어지는 잎들은 전체 순서에서도 하나의 연속한 구간을 이룬다. 자식 서브트리의 순서는 자유롭게 정할 수 있다.
정점마다 다음 세 정보를 계산한다.
서브트리 안의 모든 정점에서 자식 순서를 뒤집으면 낙엽 순서 전체가 뒤집힌다. 따라서 맨 뒤에 배치할 수 있는 빨간 잎의 최대 개수도 와 같다.
빨간 잎이 달린 끝가지에서는 가 참이고 이다. 노란 잎이 달린 끝가지에서는 가 거짓이고 이다.
끝가지가 아닌 정점 를 생각하자. 가 참인 자식 에 대해서는 서브트리 전체가 빨간 잎으로 이루어져 있으므로 가 그 잎의 개수이다. 이러한 자식들의 합을 라고 하자. 나머지 자식들의 중 가장 큰 두 값을 라고 하며, 값이 부족하면 으로 채운다.
맨 앞의 빨간 연속 구간을 최대한 길게 만들려면 빨간 잎만 있는 자식들을 먼저 배치하고, 이어서 나머지 자식 하나의 맨 앞 구간을 붙이면 된다. 노란 잎이 있는 자식을 지나고 나면 그 다음 자식의 빨간 잎은 맨 앞 구간에 포함될 수 없다. 따라서 이다.
빨간 연속 구간이 여러 자식에 걸쳐 있다면, 양 끝을 제외한 자식의 모든 잎이 빨간색이어야 한다. 따라서 노란 잎이 있는 자식은 양 끝에 최대 두 개만 사용할 수 있다. 빨간 잎만 있는 자식들을 가운데 모으고, 서로 다른 두 자식의 끝 구간과 앞 구간을 양쪽에 붙이면 를 달성한다. 각 자식 내부에서만 얻는 최댓값도 고려하면 다음과 같다.
또한 모든 자식의 가 참일 때에만 가 참이다. 끝가지부터 위로 계산하면 이 점화식이 각 상태의 정의를 만족하므로 정답은 이다.
자식들의 정보를 한 번 순회하면서 , , , 자식의 최댓값을 구할 수 있다. 전체 시간 복잡도와 공간 복잡도는 모두 이다. 최대 깊이가 일 수 있으므로 정답 코드는 반복문으로 방문 순서를 구하고, 그 역순으로 상태를 계산한다.
Solution written by GPT6