| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P191PROH - Problem H - Truy vấn trên cây |
Cho một cây gồm N đỉnh, đỉnh thứ i có giá trị là A_i. Gốc của cây này là đỉnh 1.
Ta cần thực hiện Q truy vấn như sau: Mỗi truy vấn gồm 2 số x, y (1 <= x, y <= N); và hãy cho biết tổng giá trị của tất cả các đỉnh nằm trên đường đi từ đỉnh x tới đỉnh y.
Ở đây, cây được định nghĩa là 1 đồ thị vô hướng, liên thông, và giữa 2 đỉnh bất kỳ chỉ tồn tại 1 đường đi duy nhất.
Input
Dòng đầu tiên chứa 2 số nguyên N và Q (1 <= N, Q <= 10^5).
Dòng thứ hai chứa N số nguyên là các giá trị A_i (1 <= A_i <= 2*10^4).
N-1 dòng tiếp theo, mỗi dòng chứa 2 số u, v cho biết có cạnh nối nút u và nút v (1 <= u, v <= N, u ≠ v).
Input đảm bảo thu được một cây.
Q dòng tiếp theo, mỗi dòng gồm 2 số nguyên x, y thể hiện truy vấn (1 <= x, y <= N).
Ouput
Với mỗi truy vấn, in ra đáp số trên 1 dòng.
Example
Input: 3 3 1 8 4 1 2 2 3 1 2 1 3 2 3 Output: 9 13 12
| Được gửi lên bởi: | adm |
| Ngày: | 2019-02-15 |
| 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 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
