| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P155PROH - ROUND 5H - Cây lan truyền |
Cho một cây có n nút, các nút được đánh số từ 1 đến n, gốc của cây là nút 1. Mỗi nút trên cây ban đầu đều lưu một giá trị nào đó.
Có 2 loại truy vấn được thực hiện:
- “1 x val”: cộng thêm vào nút x giá trị val.
- “2 x”: Yêu cầu trả về giá trị hiện có tại nút x.
Truy vấn cộng được thực hiện như sau: khi cộng thêm giá trị cho nút p với một giá trị val nào đó thì tất cả các nút con của nút p cộng thêm một giá trị là –val. Lặp lại tương tự thao tác cộng với các nút con của nút p, cứ thực hiện như vậy cho đến khi gặp một nút con là nút lá.
Input
Dòng đầu tiên chứa 2 số nguyên n, m (1 <= n, m <= 200000).
Dòng thứ 2 chứa n số nguyên a[1], a[2], .. , a[n] , a[i] là giá trị ban đầu tại nút i (1 <= a[i] <= 1000).
n – 1 dòng tiếp theo, mỗi dòng chứa 2 số nguyên u, v (1 <= u, v <= n) cho biết có cạnh nối giữa 2 nút này.
m dòng tiếp theo có định dạng của 1 trong 2 truy vấn (1 <= x <= n, 1 <= val <= 1000).
Output
Với mỗi truy vấn loại 2 hãy in kết quả ra trên một dòng riêng biệt.
Example
Input:5 5
1 2 1 1 2
1 2
1 3
2 4
2 5
1 2 3
1 1 2
2 1
2 2
2 4 Output:3
3
0
Giải thích test:
Giá trị của các nút ban đầu bằng [1, 2, 1, 1, 2].
Thực hiện thao tác cộng thêm 3 vào nút 2, nút 4 và nút 5 được cộng thêm giá trị bằng -3.
Giá trị các nút sau thao tác cộng đầu tiên bằng [1, 5, 1, -2, -1].Thực hiện thao tác cộng thêm 2 vào nút 1, nút 2 và nút 3 được cộng thêm giá trị -2, trong
khi đó, nút 4 và nút 5 là con của nút 2, nên được cộng thêm giá trị 2.Cuối cùng, ta thu được [3, 3, -1, 0, 1].
| Được gửi lên bởi: | adm |
| Ngày: | 2015-03-30 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2016-04-10 11:53:58
Hướng dẫn: http://mycodealgorithm.blogspot.com/2016/04/p155proh-round-5h-cay-lan-truyen.html |
|
|
2015-08-20 12:08:16 Z3r0_L0v3
Sao lại sai hả trời. Bài này ko khó nhưng test chả hiểu |
