Cây cân bằng
Nộp bài giải
Đ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ả:
Dạng bài
Ngôn ngữ cho phép
C++, Go, Java, Kotlin, Pascal, Python, Scratch
Cho cây nút, mỗi nút được gán nhãn ( hoặc ). Tìm độ lồng tối đa của bất kỳ đường đi trên cây nào tạo thành chuỗi ngoặc hợp lệ.
Độ lồng của chuỗi hợp lệ = giá trị lớn nhất của tổng tiền tố (với ( = +1, ) = -1).
Dữ liệu vào
- Dòng : Số nguyên .
- dòng tiếp: — cha của nút .
- dòng tiếp: Nhãn của nút (mỗi dòng một ký tự
(hoặc)).
Dữ liệu ra
Một số nguyên — độ lồng tối đa.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 15 1 2 1 4 4 6 7 5 9 9 11 12 13 14 ( ) ) ( ) ) ( ) ( ( ( ) ) ) ( |
3 | Đường đi tạo chuỗi ((())) có độ lồng 3. |
Bình luận