Đất nước JOI có \(N\) thị trấn, được đánh số từ \(1\) đến \(N\), và \(N-1\) con đường, được đánh số từ \(1\) đến \(N-1\). Con đường \(j\) (\(1 \le j \le N-1\)) nối hai thị trấn \(U_j\) và \(V_j\) theo cả hai chiều. Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác bằng các con đường.

Mỗi thị trấn có một cửa hàng. Cửa hàng ở thị trấn \(i\) (\(1 \le i \le N\)) bán một món quà lưu niệm với giá \(A_i\).

Có \(M\) chuyến du lịch. Chuyến \(k\) đi theo đường đơn duy nhất từ \(S_k\) đến \(T_k\), không lặp thị trấn. Với mỗi ngân sách ứng viên \(B_q\), hãy đếm số bộ \((k,u,v)\) sao cho \(u<v\), chuyến \(k\) đi qua cả \(u,v\), và \(A_u+A_v=B_q\).

Mỗi chuyến đi qua cả thị trấn xuất phát và thị trấn kết thúc. Bạn chọn một chuyến và mua đúng một món quà ở mỗi trong đúng hai thị trấn khác nhau mà chuyến đi qua, sao cho dùng hết ngân sách. Các chỉ số phải thỏa \(1 \le k \le M\) và \(1 \le u<v \le N\).

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1,\ldots,A_N\).
• \(N-1\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(U_j,V_j\).
• Dòng tiếp theo chứa số nguyên \(M\).
• \(M\) dòng tiếp theo, dòng thứ \(k\) chứa hai số nguyên \(S_k,T_k\).
• Dòng tiếp theo chứa số nguyên \(Q\).
• Dòng cuối chứa \(Q\) số nguyên \(B_1,\ldots,B_Q\).

Dữ liệu ra

In \(Q\) dòng; dòng \(q\) là số bộ thỏa ngân sách \(B_q\).

Ràng buộc

• \(2\le N\le100000\), \(1\le A_i\le N\).
• \(1\le U_j,V_j\le N\); \(N-1\) con đường tạo thành một đồ thị liên thông.
• \(1\le M\le200000\); \(1\le S_k,T_k\le N\) và \(S_k\ne T_k\).
• \(1\le Q\le2000\).
• \(1\le B_1<\cdots<B_Q\le2N\).

Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(3\) điểm: \(N,M,Q\le100\).
2. \(4\) điểm: \(N\le5000\), \(U_j=j\), \(V_j=j+1\) với mọi \(1 \le j \le N-1\).
3. \(5\) điểm: \(N\le5000\).
4. \(6\) điểm: \(Q=1\), \(U_j=j\), \(V_j=j+1\) với mọi \(1 \le j \le N-1\).
5. \(10\) điểm: \(Q=1\).
6. \(7\) điểm: \(M\le1000\), \(U_j=j\), \(V_j=j+1\) với mọi \(1 \le j \le N-1\).
7. \(12\) điểm: \(M\le1000\).
8. \(10\) điểm: \(N,M\le50000\), \(U_j=j\), \(V_j=j+1\) với mọi \(1 \le j \le N-1\).
9. \(15\) điểm: \(N,M\le50000\).
10. \(11\) điểm: \(U_j=j\), \(V_j=j+1\) với mọi \(1 \le j \le N-1\).
11. \(17\) điểm: không có ràng buộc thêm.

Ví dụ

8
1 2 3 2 1 2 3 2
2 3
7 8
4 3
1 2
7 3
2 5
6 1
4
1 4
1 6
2 5
3 8
7
1 2 3 4 5 6 16

0
0
4
2
4
1
0

8
8 2 3 6 1 4 1 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1
1 8
5
2 4 5 10 15

1
2
3
3
1

Nguồn

JOI 2025/2026 Final Stage, Cuộc thi 2, bài JOI Tour 2, Japanese Committee for IOI. Bản dịch được đối chiếu với đề gốc tiếng Nhật và bản tiếng Anh. Đề gốc, bản dịch và bản điều chỉnh được cung cấp theo CC BY-SA 4.0.