DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

봄 여름 가을 겨울

Back to problem

Editorial

각 정점 vvv를 루트로 하는 서브트리에서 떨어지는 잎들은 전체 순서에서도 하나의 연속한 구간을 이룬다. 자식 서브트리의 순서는 자유롭게 정할 수 있다.

정점마다 다음 세 정보를 계산한다.

  • FvF_vFv​: 서브트리의 모든 잎이 빨간색인지 여부.
  • EvE_vEv​: 서브트리의 낙엽 순서 맨 앞에 빨간 잎을 연속해서 배치할 수 있는 최대 개수.
  • AvA_vAv​: 서브트리의 낙엽 순서 안에서 빨간 잎이 연속해서 떨어지는 개수의 최댓값.

서브트리 안의 모든 정점에서 자식 순서를 뒤집으면 낙엽 순서 전체가 뒤집힌다. 따라서 맨 뒤에 배치할 수 있는 빨간 잎의 최대 개수도 EvE_vEv​와 같다.

빨간 잎이 달린 끝가지에서는 FvF_vFv​가 참이고 Ev=Av=1E_v=A_v=1Ev​=A이다. 노란 잎이 달린 끝가지에서는 가 거짓이고 이다.

끝가지가 아닌 정점 vvv를 생각하자. FuF_uFu​가 참인 자식 uuu에 대해서는 서브트리 전체가 빨간 잎으로 이루어져 있으므로 EuE_uEu​가 그 잎의 개수이다. 이러한 자식들의 합을 라고 하자. 나머지 자식들의 중 가장 큰 두 값을 라고 하며, 값이 부족하면 으로 채운다.

맨 앞의 빨간 연속 구간을 최대한 길게 만들려면 빨간 잎만 있는 자식들을 먼저 배치하고, 이어서 나머지 자식 하나의 맨 앞 구간을 붙이면 된다. 노란 잎이 있는 자식을 지나고 나면 그 다음 자식의 빨간 잎은 맨 앞 구간에 포함될 수 없다. 따라서 Ev=S+t1E_v=S+t_1Ev​=S+t1​이다.

빨간 연속 구간이 여러 자식에 걸쳐 있다면, 양 끝을 제외한 자식의 모든 잎이 빨간색이어야 한다. 따라서 노란 잎이 있는 자식은 양 끝에 최대 두 개만 사용할 수 있다. 빨간 잎만 있는 자식들을 가운데 모으고, 서로 다른 두 자식의 끝 구간과 앞 구간을 양쪽에 붙이면 S+t1+t2S+t_1+t_2S+t1​+t2​를 달성한다. 각 자식 내부에서만 얻는 최댓값도 고려하면 다음과 같다.

Av=max⁡(max⁡u는 v의 자식Au, S+t1+t2).A_v=\max\left(\max_{u\text{는 }v\text{의 자식}} A_u,\ S+t_1+t_2\right).Av​=max(u는 v의

또한 모든 자식의 FuF_uFu​가 참일 때에만 FvF_vFv​가 참이다. 끝가지부터 위로 계산하면 이 점화식이 각 상태의 정의를 만족하므로 정답은 A1A_1A이다.

자식들의 정보를 한 번 순회하면서 SSS, t1t_1t1​, t2t_2t2​, 자식의 AuA_u 최댓값을 구할 수 있다. 전체 시간 복잡도와 공간 복잡도는 모두 이다. 최대 깊이가 일 수 있으므로 정답 코드는 반복문으로 방문 순서를 구하고, 그 역순으로 상태를 계산한다.

Solution written by GPT6

v
​
=
1
FvF_vFv​
Ev=Av=0E_v=A_v=0Ev​=Av​=0
EuE_uEu​
SSS
EuE_uEu​
t1,t2t_1,t_2t1​,t2​
000
 
자식
max
​
Au​
,
 
S
+
t1​
+
t2​
)
.
1
​
Au​
O(N)O(N)O(N)
N−1N-1N−1