레이팅 미적용농부 존은 여러 소 품종의 진화에 대한 광범위한 연구를 수행했다. 그 결과는 \(1\ldots N\)으로 번호가 매겨진 \(N\)개(\(2\le N\le 10^5\))의 노드를 갖는 루트 있는 트리이며, 각 노드는 하나의 소 품종에 대응한다. 각 \(i\in [2,N]\)에 대해, 노드 \(i\)의 부모는 노드 \(p_i\) (\(1\le p_i
트리의 모든 노드 \(i\)는 정수 개수의 반점 \(s_i\)를 갖는 품종과 연관되어 있다. 트리의 "불균형"은 \(j\)가 \(i\)의 조상인 모든 노드 쌍 \((i,j)\)에 대한 \(|s_i-s_j|\)의 최댓값으로 정의된다.
농부 존은 각 품종의 \(s_i\)의 정확한 값은 모르지만, 그 값들의 하한과 상한은 알고 있다. 각 노드에 정수 값 \(s_i \in [l_i,r_i]\) (\(0\le l_i\le r_i\le 10^9\))를 배정하여 트리의 불균형을 최소화하는 것이 당신의 임무이다.
Problem credits: Andrew Wang
채점 방식
- 테스트 케이스 3-4는 모든 \(i\)에 대해 \(l_i=r_i\)를 만족한다.
- 테스트 케이스 5-6은 모든 \(i\)에 대해 \(p_i=i-1\)을 만족한다.
- 테스트 케이스 7-16은 추가 제약이 없다.
각 서브태스크 안에서, 테스트 케이스의 앞쪽 절반은 \(B=0\)을, 나머지는 \(B=1\)을 만족한다.
Problem credits: Andrew Wang
첫째 줄에 독립적으로 풀어야 하는 테스트 케이스의 수 \(T\) (\(1\le T\le 10\))와 정수 \(B\in \{0,1\}\)이 주어진다.
각 테스트 케이스는 \(N\)이 주어지는 줄로 시작하며, 이어서 \(N-1\)개의 정수 \(p_2,p_3,\ldots,p_N\)이 주어진다.
다음 \(N\)개의 줄에는 두 정수 \(l_i\)와 \(r_i\)가 주어진다.
모든 테스트 케이스에 걸친 \(N\)의 합은 \(10^5\)를 초과하지 않음이 보장된다.
각 테스트 케이스에 대해, \(B\)의 값에 따라 한 줄 또는 두 줄을 출력한다.
각 테스트 케이스의 첫째 줄에는 최소 불균형을 출력한다.
\(B=1\)이면, 위의 불균형을 달성하는 반점 배정 \(s_1,s_2,\ldots, s_N\)을 공백으로 구분된 \(N\)개의 정수로 한 줄 더 출력한다. 유효한 배정이면 무엇이든 정답으로 인정된다.
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 103
1
4For the first test case, the minimum imbalance is \(3\). One way to achieve
imbalance \(3\) is to set \([s_1,s_2,s_3]=[4,1,7]\).
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 103
3 1 6
1
6 5 5 5 5
4
5 1 9This input is the same as the first one aside from the value of \(B\). Another way
to achieve imbalance \(3\) is to set \([s_1,s_2,s_3]=[3,1,6]\).