Cân Bằng Cây

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John có một cây có gốc với $N$ đỉnh ( $2 \leq N \leq 10^{5}$ ). Mỗi đỉnh $i$ có cha là $p_{i}$ và cần được gán một giá trị nguyên $s_{i} \in [l_{i}, r_{i}]$ .

"Độ mất cân bằng" được định nghĩa là hiệu tuyệt đối lớn nhất $| s_{i} - s_{j} |$ giữa bất kỳ đỉnh $i$ và tổ tiên $j$ của nó.

Hãy gán giá trị cho các đỉnh sao cho độ mất cân bằng là nhỏ nhất.

Dữ liệu vào

Dòng 1: Hai số nguyên $T$ (số test case) và $B \in {0, 1}$
Với mỗi test case:
- Dòng 1: Số nguyên $N$
- Dòng 2: $N - 1$ số nguyên $p_{2}, p_{3}, \dots, p_{N}$
- $N$ dòng tiếp theo: Hai số nguyên $l_{i}$ và $r_{i}$ cho mỗi đỉnh

Dữ liệu ra

Với mỗi test case:

Dòng 1: Độ mất cân bằng tối thiểu
Nếu $B = 1$ : Dòng 2 gồm $N$ số nguyên — một cách gán hợp lệ

Ràng buộc

$1 \leq T \leq 10$
Tổng $N$ qua tất cả test case $\leq 10^{5}$
$0 \leq l_{i} \leq r_{i} \leq 10^{9}$
Test 1-5: $B = 0$
Test 6-16: $B = 1$

Ví dụ

Input	Output	Giải thích
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	Test 1: 3 đỉnh, gốc có $[0, 100]$ , hai con có $[1, 1]$ và $[6, 7]$ . Gán tối ưu cho gốc là 4, độ mất cân bằng = $max (\| 4 - 1 \|, \| 4 - 7 \|) = 3$ .

Bình luận

Không có bình luận tại thời điểm này.