Truy vấn đường đi II
Nộp bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.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 một cây gồm đỉnh, gốc tại đỉnh 1. Mỗi đỉnh có một giá trị ban đầu. Xử lý thao tác:
- Loại 1: Cập nhật giá trị của một đỉnh.
- Loại 2: Tìm giá trị lớn nhất trên đường đi giữa hai đỉnh.
Dữ liệu vào
Dòng đầu chứa hai số nguyên và .
Dòng thứ hai chứa số nguyên là giá trị ban đầu của các đỉnh từ đến .
dòng tiếp theo, mỗi dòng chứa hai số nguyên và mô tả một cạnh của cây.
dòng tiếp theo, mỗi dòng là một thao tác:
1 s x— cập nhật giá trị đỉnh thành .2 a b— tìm giá trị lớn nhất trên đường đi giữa và .
Dữ liệu ra
Với mỗi thao tác loại 2, in ra giá trị lớn nhất. Tất cả kết quả in trên một dòng, cách nhau bởi dấu cách.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 3 2 4 1 3 3 1 2 1 3 2 4 2 5 2 3 5 1 2 2 2 3 5 |
4 3 | Đường 3→5: đỉnh 3(1),1(2),2(4),5(3), max=4. Sau cập nhật đỉnh 2 thành 2: max đường 3→5 = max(1,2,2,3)=3. |
| 4 2 3 1 4 2 1 2 1 3 1 4 2 2 3 2 1 4 |
4 3 | Đường 2→3: đỉnh 2(1),1(3),3(4), max=4. Đường 1→4: đỉnh 1(3),4(2), max=3. |
Bình luận