Tree Robber
Thời gian
1s
Bộ nhớ
1GB
Đọc vào (Input)
Bàn phím
Ghi ra (Output)
Màn hình
Đề bài
Cho một cây vô hướng gồm N đỉnh, đánh số từ 1 tới N. Mỗi đỉnh i có một giá trị nguyên ai.
Ta gọi một tập đỉnh là hợp lệ nếu không có hai đỉnh nào trong tập kề nhau trên cây. Giá trị của một tập hợp lệ là tổng các giá trị ai của những đỉnh được chọn.
Có Q thao tác online thuộc một trong hai loại sau:
- 1 x y: gán ax = y;
- 2 u v: xét đường đi đơn từ u tới v, hãy tìm giá trị lớn nhất của một tập đỉnh hợp lệ nằm hoàn toàn trên đường đi đó. Hãy in ra đáp án cho mỗi truy vấn loại 2. Tập rỗng được xem là hợp lệ.
Input
- Dòng đầu tiên chứa hai số nguyên N, Q. (1 ≤ N, Q ≤ 2 × 105)
- Dòng thứ hai chứa N số nguyên a1, a2, ..., aN. (−109 ≤ ai ≤ 109)
- N − 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v mô tả một cạnh của cây. (1 ≤ u, v ≤ N)
- Q dòng tiếp theo, mỗi dòng là một thao tác thuộc một trong hai dạng đã mô tả.
Output
- Với mỗi truy vấn loại 2, in ra một số nguyên duy nhất là giá trị lớn nhất có thể thu được.
Ví dụ
Input 1
5 3 3 1 5 2 4 1 2 2 3 2 4 4 5 2 3 5 1 3 10 2 1 5
Output 1
9 7
Input 2
7 8 5 -2 7 3 4 -1 6 1 2 1 3 2 4 2 5 3 6 6 7 2 4 7 1 2 10 2 4 5 1 6 20 2 7 5 1 5 -100 2 4 5 2 1 7
Output 2
16 10 30 10 25
Ràng buộc & Tóm tắt
Giải thích:
- Truy vấn đầu tiên xét đường đi từ 3 tới 5 gồm các đỉnh 3,2,4,5.
- Sau khi cập nhật
1 3 10, giá trị tại đỉnh 3 thay đổi nên đáp án của truy vấn sau cũng thay đổi theo
Ràng buộc:
- Subtask 1 (20% điểm): N, Q ≤ 2000.
- Subtask 2 (20% điểm): Cây là một đường thẳng.
- Subtask 3 (20% điểm): Không có thao tác loại 1.
- Subtask 4 (40% điểm): Không có ràng buộc thêm.
Thông tin bài tập
Mã bài:
tree-robber
Mức độ:
Nâng cao
Điểm số:
100 đ
