P7288 "EZEC-5" The Anger of Trees

Little L is always humbly beaten up by powerful people, including Little Y.

Little L and Little Y are good friends. One day, Little L brought a weighted tree with $n$ vertices. The weight of vertex $u$ is $a_u$. However, Little Y hates trees, so without saying anything, he directly cut one edge of the tree. Little L was very angry, but in order to stay polite, he decided to reconnect this edge after finishing his work. However, he always makes mistakes in his operations: not only can he not reconnect it, but he will also cut another edge. As a result, the tree is split into $3$ connected components. Little Y could not stand it anymore. After cutting an edge, he started thinking about a difficult problem for him. He wants to know: after cutting the $x$-th edge, since Little L will still mistakenly cut one more edge, what is the **sum over all possible cases of the product of the sums of weights of the 3 connected components formed in the end**. That is, let the three connected components be $a, b, c$. Given that one edge has already been cut, compute the total sum of $$ (\sum_{u\in a} a_u)\times (\sum_{u\in b} a_u) \times (\sum_{u\in c} a_u) $$ over all possibilities of the second cut. Because of his anger, every time you finish the calculation, Little L ignores the answer you computed for Little Y. So Little Y has to restore the graph back to the original tree, cut another edge, and you must help Little Y compute it again, i.e., perform another (possibly different) query. You need to help Little Y for a total of $q$ times, meaning you must answer $q$ queries. Also, because both Little L and Little Y dislike very large numbers, please output this total sum modulo $99991$. Also, because printing is too time-consuming, you only need to output the sum and the xor-sum of the answers (each taken modulo $99991$) over all queries.

The first line contains two positive integers $n, q$. The second line contains $n$ non-negative integers representing $a_{1,2,...,n}$. In the following $n-1$ lines, the $i$-th line contains two positive integers $(u, v)$, representing the $i$-th edge $(u, v)$. Then there are $q$ positive integers. The $i$-th integer represents the edge cut in the $i$-th query. Note that all queries are independent.

Output two lines in total. The first line outputs the sum of all answers modulo $99991$ (note that the final output may be greater than or equal to $99991$). The second line outputs the xor-sum of all answers modulo $99991$.

**Sample Explanation** For the first query of Sample 1, the first edge (i.e., edge $(1, 2)$) has already been cut. If Little L cuts edge $(2, 3)$ again, then the product of the sums of weights of the 3 connected components is $1\times 2\times (3+4)=14$. If Little L cuts edge $(3, 4)$ again, then the product is $1\times (2+3)\times 4=20$. So the output is $14+20=34$. For the second query of Sample 1, the second edge (i.e., edge $(2, 3)$) has already been cut. If Little L cuts edge $(1, 2)$ again, then the product is $1\times 2\times (3+4)=14$. If Little L cuts edge $(3, 4)$ again, then the product is $(1+2)\times 3\times 4=36$. So the output is $14+36=50$. Similarly, we can compute the third query of Sample 1, whose answer is $20+36=56$. So the total sum of the three answers is $140$, and the xor-sum is $40$. --- **Constraints** $\texttt{Subtask 1 (1 pts) } a_i=0$。 $\texttt{Subtask 2 (5 pts) } n,q\le 300$。 $\texttt{Subtask 3 (14 pts) } n\le 300$。 $\texttt{Subtask 4 (20 pts) } n\le 5000$。 $\texttt{Subtask 5 (10 pts) } u=v-1$。 $\texttt{Subtask 6 (50 pts) }$ No special constraints. For all data, $2 \le n, q \le {10}^6$ and $0 \le a_i \le {10}^6$. --- idea by lgswdn tested by LHQing, Karry5307 Translated by ChatGPT 5