Truy vấn cây con
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ính tổng giá trị tất cả các đỉnh trong cây con gốc tại một đỉ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 s— tính tổng giá trị cây con gốc tại .
Dữ liệu ra
Với mỗi thao tác loại 2, in ra tổng giá trị cây con.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 3 4 2 5 2 1 1 2 1 3 3 4 3 5 2 3 1 5 3 2 3 |
8 10 |
Cây con gốc 3 gồm đỉnh 3,4,5 có tổng 5+2+1=8. Sau khi cập nhật đỉnh 5 thành 3, tổng là 5+2+3=10. |
| 3 3 1 2 3 1 2 2 3 2 1 1 3 10 2 2 |
6 12 |
Cây con gốc 1 gồm tất cả 3 đỉnh, tổng 1+2+3=6. Sau khi cập nhật đỉnh 3 thành 10, cây con gốc 2 gồm đỉnh 2,3 có tổng 2+10=12. |
Bình luận