U433128 Range Sum Queries on Trees

You are given a rooted tree consisting of $n$ nodes numbered $1, \dots, n$. Node $1$ is the root. Every node has a value, where the value of node $u$ is $a_u$. A subtree $u$ consists of node $u$ and all nodes who have $u$ as one of their ancestors. You are then given $q$ queries, each consisting of two integers $x$ and $k$. Your task is to find the sum of the values of all nodes in the subtree $x$ whose distance to $x$ is less than $k$. That is, let $d_v$ denote the depth of node $v$, and $S_x$ denote the set of all nodes in the subtree $x$. You have to find $$\sum_{(v \in S_x) \wedge (d_v - d_x < k)} a_v.$$

Each test consists of $T$ independent test cases. The first line of each test case contains an integer $n$. The next line contains the array of integers $a_1, \dots a_n$. The $i$th line of the following $n - 1$ lines contains two integers $u_i, v_i$, indicating that there is an edge connecting nodes $u_i$ and $v_i$ in the given tree. The next line contains an integer $m$. The $j$th line of the following $m$ lines contains two integers $x_j, k_j$, indicating a query.

For each test case, print $m$ lines - the answer.

- $1 \leq n, q \leq 2 \cdot 10^5$ - $1 \leq a_i \leq 10^9$ $(1 \leq i \leq n)$ - $1 \leq u, k \leq n$ - The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. - The sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.