Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.