Time Limit: 10 Seconds
Memory Limit: 524288 KB
You are given a tree with n vertices. The i-th vertex has a non-negative weight wi.
You are given q quereis. For each query, you are given two integers x and d. You need to find the number of such vertex y that:
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains two integers n and q (1 ≤ n, q ≤ 100000) — the number of vertices and the number of queries.
The second line contains n integers w1, w2, ..., wn (0 ≤ wi ≤ 109).
Each of the following n - 1 lines describing edges contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) meaning that there is a edge connecting vertex u and vertex v.
Each of the next q lines contains two integers x and d (1 ≤ x ≤ n, 0 ≤ d ≤ n).
It is guaranteed that the total number of vertices in the input doesn't exceed 5 × 105, and the total number of queries also doesn't exceed 5 × 105. The number of test cases in the input doesn't exceed 500.