P9099 [PA 2020] Huge Tree

**This problem is translated from [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Round 3 [Ogromne drzewo](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/ogr/).** Byteasar bought his girlfriend Algolina a huge Christmas tree. This is a very unusual gift, but Byteasar is an algorithmist, and Algolina is already used to such surprises. As you may have guessed, this tree is not a plant, but a connected acyclic graph. It is very large, but it can be described in an organized way. Its vertices have $n$ levels. The first level contains only one vertex, which is the root of the tree. The children of each vertex are only on the next level, except for the vertices on the last level, which are leaves. For each $i$ in the range $[1, n - 1]$, every vertex on level $i$ has $a_i$ children. Algolina wants Byteasar to know how satisfied she is with the gift, so she decides to play a game with him. Algolina chooses a vertex $A$ in the tree, and Byteasar chooses a vertex $B$ (possibly the same as Algolina’s). Now, starting with Algolina, they will take turns recoloring vertices of the tree: Algolina uses red, and Byteasar uses blue. At the beginning of the game, all vertices are white. Each vertex will be recolored exactly once, either by Algolina or by Byteasar. At any time, the player whose turn it is may recolor any white vertex with their own color, including vertex $A$ and vertex $B$. Once all vertices have been recolored, they compute their scores. Algolina’s score (denoted by $S_A$) is the sum of distances from all red vertices to vertex $A$, and Byteasar’s score (denoted by $S_B$) is the sum of distances from all blue vertices to vertex $B$. The distance between two vertices is the number of edges on the shortest path between them. Algolina’s goal is to make her score exceed Byteasar’s by as much as possible, i.e. to maximize $S_A - S_B$, while Byteasar’s goal is to minimize it. Byteasar quickly points out that this is a finite perfect-information game, so assuming both players play optimally, the final score difference can be determined. He hopes you can help compute this value. Since it may be very large, you should output it modulo $10^9+7$. Also, since forgetting the gift after just one game would be unpleasant, you need to compute the final score difference for many different choices of vertices $A$ and $B$.

The first line contains two integers $n, q$, representing the number of levels of the tree and the number of queries. The second line contains $n-1$ integers $a_1, a_2, \cdots, a_{n-1}$, as described above. The next $q$ lines each describe $A, B$. You may notice that the final result depends only on vertices $A, B$ and on which level their lowest common ancestor lies, so each line provides three integers $W_A, W_B, W_{\operatorname{lca}(A,B)}$.

Output $q$ lines. The $i$-th line should contain the answer to the $i$-th query, modulo $10^9+7$.

#### Sample 1 Explanation In the sample, the tree has three levels: one vertex on the first level, three vertices on the second level, and six vertices on the third level. For the second query, both Algolina and Byteasar choose the root. Under optimal play, they should choose vertices in non-increasing order of level. In the end, the result is $(2 + 2 + 2 + 1 + 1) - (2 + 2 + 2 + 1 + 0) = 1$. For the third query, the answer is $-4$, but you should output $-4 \bmod (10^9+7) = 10^9+3$. ------------ #### Constraints **This problem uses bundled testdata.** - For some subtasks, the tree has at most $3\times 10^5$ vertices, and $q\le 100$. - For some other subtasks, $q\le 100$. For each of the above cases, there is at least one such subtask. For $100\%$ of the testdata, it is guaranteed that $2\le n\le 3\times 10^5$, $1\le q\le 3\times 10^5$, $2\le a_i\le 3\times 10^5$, and $1\le W_{\operatorname{lca}(A,B)}\le W_A, W_B\le n$. Translated by ChatGPT 5