페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5321
스페셜 저지

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

문제

트리의 각 노드는 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의 값과 그 때의 불균형 값을 구하시오.​


입력

첫 번째 줄에 테스트 케이스의 수 T와 출력의 형식을 뜻하는 정수 B∈{0, 1}​가 입력된다. (1≤T≤10)

각 테스트 케이스의 첫 번째 줄에는 N이 입력되고, 두 번째 줄에는 N−1개의 정수 p_2, p_3, …, p_N이 입력된다. (2≤N≤10^5)

다음 N 줄에 걸쳐 두 개의 정수 l_i 및 r_i가 입력된다. (0 ≤ l_i ≤ r_i ≤ 10^9)

입력은 모든 테스트 케이스의 N 합계가 10^5를 초과하지 않는다.


출력

각 테스트 케이스에 대해 B 값에 따라 한 줄 또는 두 줄을 출력한다.

각 테스트 케이스의 첫 번째 행은 최소 불균형을 출력한다.

만약 B=1이면 트리의 불균형을 최소화하기 위해 각 노드에 할당되는 정수 s_1,s_2,… s_N 를 ​N개의 공백으로 구분하여 출력한다. 

가능한 답은 모두 정답으로 인정된다.


예제1

입력
3 0

3

1 1

0 100

1 1

6 7

5

1 2 3 4

6 6

1 6

1 6

1 6

5 5

3

1 1

0 10

0 1

9 10
출력
3

1

4

첫 번째 하위 테스트 사례의 경우 최소 불균형은 3입니다. 

3의 불균형을 달성하는 한 가지 방법은 [s1,s2,s3]=[4,1,7]을 만드는 것입니다. 


예제2

입력
3 1

3

1 1

0 100

1 1

6 7

5

1 2 3 4

6 6

1 6

1 6

1 6

5 5

3

1 1

0 10

0 1

9 10
출력
3

3 1 6

1

6 5 5 5 5

4

5 1 9

이 테스트 케이스는 B 값을 제외하고 첫 번째 테스트 케이스와 정확히 동일합니다. 

3의 불균형을 달성하는 또 다른 방법은 [s1,s2,s3]=[3,1,6]으로 만드는 것입니다. 


출처

USACO 2022 US Open Gold

역링크 공식 문제집만