트리의 각 노드는 1부터 N까지의 번호가 매겨져있고, 루트 노드는 1으로 정해져있다.

각 i∈[2, N]에 대해 노드 i의 부모는 노드 p_i(1 ≤ p_i < i)이다.

해당 트리의 각 노드에는 0에서 10^9 사이에 하나의 정수 값이 있는데, i번 노드의 해당 정수 값을 s_i라고 한다.

트리의 "불균형"은 모든 노드 쌍(i, j) 중 |s_i − s_j|의 최댓값으로 정의되며, 여기서 j는 i의 부모이거나 조상인 경우이다.

각 노드별로 s_i에 대한 정확한 값을 모르고 해당 값의 하한과 상한인 l_i와 r_i를 알고 있을 때, 트리의 불균형을 최소화하는 s_i의 값과 그 때의 불균형 값을 구하시오.

트리의 균형화 (Balancing a Tree) timer 2s memory 256MB

트리의 균형화 (Balancing a Tree) 2s 256MB