DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

봄 여름 가을 겨울

문제로 돌아가기

해설

각 정점 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