Boring tree queries#11544
Given a tree with vertices. Each vertex of the tree has a single number written on it.
In this problem you must answer queries. Each query is described by three numbers , and . To answer the query, first write down the numbers written on the vertices in a simple path from to in the order they appear. Then the answer to the query is calculated in this way: add the first numbers of the obtained sequence, subtract the next numbers, then again add the next numbers, and then again subtract the next numbers, and so on. It is guaranteed that the number of vertices in a simple path from to is divisible by .
The first line contains two integers n~(1 \le n \le 10^5) — the number of vertices in the tree, and q~(1 \le q \le 10^5) — the number of queries.
The second line contains a sequence of integers a_1, a_2, \dots, a_n~(1 \le a_i \le 10000) — the numbers written on vertices.
Then follow n-1 lines, describing the tree edges. Each line contains a pair of integers x_i, y_i~(1 \leq x_i,y_i \leq n, x_i \ne y_i) — the vertices connected by an edge.
The last lines describe the queries, the -th line contains three numbers u_i, v_i, k_i~(1 \le u_i, v_i, k_i \le n).
Output lines, -th line contains the answer to the -th query.
Example 1
Example 2