BOJ 24976 - Balancing a Tree

그냥 트리에서 어쩌다 저쩌다보면 맞을 수 있는 문제같다.
내 풀이말고 에디토리얼을 그냥 정리해보겠다.
li=ri
이 경우엔 모든 노드에 대해 조상의 가장 작은 값과 가장 큰 값을 계속 관리해 O(n)으로 풀 수 있다.
B=0
정답의 lower bound를 고려한다.
어떤 자손 조상인 i,j 에 대해 다음과 같은 식이 성립한다.
answer≥Max(Maxi,j,related(0,li−ri),⌈2Maxili−Miniri⌉)
일단 뒤에 ⌈⌉ 부분은 어떤 i 중 가장 작은 li 와 어떤 i중 가장 큰 ri 의 차이의 절반보다는 항상 커야하므로 옳다.
항상 i→1→j 를 고려하면 그렇다. 따라서 이 경우는 i,j가 조상-자손 관계가 아니여도 된다.
전자는 조상 li,ri 과 자손 lj,rj 가 구간이 겹치지 않는다면 그 차만큼보다 정답은 커야하므로 옳다.
이 lower bound가 정답임을 항상 구성할 수 있고 아래서 설명된다.
B=1
R=Miniri 라 하고 L=Maxili 라 하고 M=⌊2L+R⌋라 한다.
모든 i에 대해 Wi=Max(li,Min(M,ri)) 를 두는 정답이 항상 성립한다.
만약 R≥L 이라면 정답은 항상 0 이다.
그렇지 않다면 모든 i에 대해 ∣Wi−M∣≤⌈2L−R⌉ 임을 관찰한다.
어떤 조상-자손 관계인 i,j 에 대해 Max(Wi,Wj)≤M 이라면
∣Wi−Wj∣≤⌈2L−R⌉≤answer 에 의해 옳다.
유사하게 Min(Wi,Wj)≥M 일 때도 성립한다.
Wi>M, Wj<M 이라면 Wi=li 이고 Wj=rj 이므로 ∣Wi−Wj∣=li−rj≤answer 라서 성립한다.
솔직히 뭔말인지 모르겠다;
Comments