410197: GYM103973 G Math Learning

Walk Alone is afraid of math, especially memorizing formulas. In Walk Alone's math textbook, there are $$$n$$$ formulas connected with $$$n-1$$$ edges, which form a tree rooted at the first formula. To handle the $$$i$$$-th formula, he must remember all formulas in its subtree, including the formula itself, and memorizing the $$$i$$$-th formula consumes $$$h_i$$$ energy.

One day after math class, Walk Alone is assigned with $$$m$$$ math problems as his homework, and he should complete them in order. To complete the $$$i$$$-th problem, he needs to handle the $$$x_i$$$-th formula. However, when he is solving the $$$i$$$-th problem, he can only remember all formulas used in the recent $$$k_i$$$ problems. Formally speaking, he remembers formula $$$u$$$ if and only if there exists a positive integer $$$p$$$ such that $$$i-k_i\le p<i$$$ and $$$u$$$ is in the subtree of $$$x_p$$$. For all formulas in the subtree of $$$x_i$$$ that he does not remember, he will consume energy to memorize them.

Walk Alone wants to know the amount of energy he should consume to finish each problem.

The first line contains two integers $$$n\ (1\le n\le 10^6)$$$ and $$$m\ (1\le m\le 2\cdot 10^5)$$$, indicating the number of formulas and problems, respectively.

The second line contains $$$n$$$ integers, the $$$i$$$-th of which, $$$h_i\ (1\le h_i\le 10^9)$$$, indicates the energy needed to memorize the $$$i$$$-th formula.

Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v\ (1\le u,v\le n)$$$, indicating an edge between $$$u$$$ and $$$v$$$.

The $$$i$$$-th of the following $$$m$$$ lines contains two integers $$$x_i\ (1\le x_i\le n)$$$ and $$$k_i\ (0\le k_i\le m)$$$ as described above.

Output the amount of energy Walk Alone needs to consume to finish each problem.

5 5
1 2 4 8 16
1 2
1 3
2 4
2 5
1 1
2 1
4 1
5 1
1 2

31
0
0
16
7