LCA Problem Revisited#5218
Given a rooted tree with (1 \leq n \leq 100\,000) vertices, labeled from to n-1, you need to respond to (1 \leq m \leq 10\,000\,000) queries regarding the lowest common ancestor (LCA) of pairs of vertices.
The queries are generated as follows: You are provided with numbers a_1, a_2, and constants , , and . The sequence a_3, \ldots, a_{2m} is generated using the formula: a_i = (x \cdot a_{i-2} + y \cdot a_{i-1} + z) \bmod n. The first query is \langle a_1, a_2 \rangle. If the answer to the (i-1)-th query is , then the -th query is \langle (a_{2i-1} + v) \bmod n, a_{2i} \rangle.
The first line contains two integers: and . The root of the tree is vertex . The second line lists n-1 integers, where the -th integer indicates the parent of vertex . The third line provides two integers, a_1 and a_2, each in the range from to n-1. The fourth line contains three non-negative integers: , , and , each not exceeding 10^9.
Output the sum of the vertex numbers that are the answers to all the queries.
Example 1