Take the prefix sum of $$$a$$$, and then do "Gaussian elimination".

We do all calculations modulo $$$10^9+7$$$.

Let the prefix sum of $$$a_1,a_2,\dots,a_n$$$ be $$$p_1,p_2,\dots,p_n$$$; that is, $$$p_i=\sum\limits_{j=1}^i a_i$$$.

Then, for $$$i=2,3,\dots,n$$$, we can express the constraint given to us as $$$x_ip_i-y_ip_{i-1}=z_i-y_ip_n$$$, or $$$p_i=\frac{z_i-y_ip_n+y_ip_{i-1}}{x_i}$$$. On the other hand, if $$$i=1$$$, we instead have $$$x_1a_1+y_1p_n=z_1$$$, so $$$p_n=\frac{z_1-x_1a_1}{y_1}$$$. Substituting this into the recurrence for $$$p_i$$$ we get

On the other hand, $$$p_1=a_1$$$. Therefore, using this recurrence we can determine sequences $$$m_i$$$ and $$$b_i$$$ such that $$$p_i=m_ia_1+b_i$$$, even though $$$a_1$$$ is unknown! Now, we have two constraints on $$$p_n$$$: $$$p_n=\frac{z_1-x_1a_1}{y_1}$$$ and $$$p_n=m_na_1+b_n$$$. If there is a unique solution for $$$a_1$$$ now, we can plug it in into all $$$p_i$$$, getting the unique solution for all $$$a_i$$$; otherwise, $$$a_1$$$ either doesn't exist or is indeterminate. In the latter case, we output $$$10^9+7$$$, because any $$$a_1$$$ still uniquely determines $$$a$$$.

A lot of alternate universes are identical: at any time they share the same set of characters that are canonically alive. Don't process redundant universes.

It seems very difficult to predict the effect of deducting one life due to a butterfly-like effect. The constraints hint at an $$$O(nm)$$$ solution.

Firstly, notice that if we instead consider the deduction to be before an event, it becomes obvious that many universes are useless. For example, the alternate universe $$$i-1,v$$$ where $$$v\neq u_i$$$ and $$$v\neq v_i$$$ will be no different from the alternate universe $$$i,v$$$. Furthermore, the effect of $$$i-1,v_i$$$ and $$$i,v_i$$$ are also both the same; therefore the only universes that "matter" are $$$i-1,u_i$$$.

For each character we can keep track of the last alternate universe they were affected in: $$$(i-1,u_i),(i-2,u_i),\dots$$$; this tells us the number of universes that are identical to $$$i-1,u_i$$$. For each $$$i-1,u_i$$$ we can then do brute force. This is $$$O(n^2+m)$$$, which is enough for the first three subtasks.

Lastly, the universe only matters if this specific deduction changes the aliveness of $$$u_i$$$; otherwise $$$i-1,u_i$$$ will still be identical to $$$i,u_i$$$. Over the $$$n$$$ events this change can happen at at most $$$m$$$ events, so there are effectively only $$$m$$$ universes that matter, reducing the time to $$$O(nm)$$$ which is enough to pass.

The next optimization would seem to be replacing the brute force for each universe with some magic data structure on trees or graphs, but I don't know how to do that :( if there is a better solution pls tell me in the comments

Express the ordinary dp for each node as a function of $$$x$$$.

Consider dp on trees; if the dp information for each node is a function of $$$x$$$, we get

Observe that this is a piecewise linear function in terms of $$$x$$$; furthermore, if the size of the subtree of $$$u$$$ is $$$s_u$$$, then $$$f_u(x)$$$ has at most $$$s_u-1$$$ "joints" and thus can be expressed with $$$s_u$$$ pieces. The problem now is to represent $$$f_u(x)$$$ in such a way that we can evaluate it quickly and merge them together. Due to the presence of $$$\max(0,f_v(x))$$$, the obvious choice is to express $$$f_u(x)$$$ as the prefix sum of a set of linear functions.

If we use balanced binary search trees, then merging them together can be done with the small-to-large trick, and taking max $$$0$$$ of it can be done by cutting of a prefix of linear functions and adding an appropriate linear function at $$$0$$$. This would solve the problem in $$$O(n\log^2 n+q\log n)$$$, which is enough for the first four subtasks.

We can easily reduce the time complexity of taking max $$$0$$$ by walking on the bbst and disconnecting subtrees of the bbst; the bottleneck then is merging. There are some bbsts that support fast merging; here we use the technique of merging segment trees by TLE; the benefit is mainly that the implementation is relatively simple and only costs an extra log factor on memory. Querying the function would thus reduce to taking the sum of an interval of linear functions, and all other operations can be done in $$$O(\log n)$$$, thus solving the problem in $$$O((n+q)\log n)$$$.

This is equivalent to asking the number of $$$i,j$$$ that are only reachable if we pass through an additional edge. For a certain $$$i$$$, what $$$j$$$ satisfy this condition?

Call a pair $$$(i,j)$$$ good if there exists a path from $$$i$$$ to $$$j$$$ in $$$T\cup U$$$ and all such paths need to pass through an additional edge. If $$$(i,j)$$$ is good and there exists a path from $$$j$$$ to $$$k$$$ in $$$T$$$, it follows that $$$(i,k)$$$ is good, as ancestry in $$$T$$$ is transitive. Therefore, for a fixed $$$i$$$, the $$$j$$$ such that $$$(i,j)$$$ is good form a set of disjoint subtrees of $$$T$$$. It follows that the roots of these subtrees must be the endpoint of an additional edge.

Define the representative of a good pair $$$(i,j)$$$ as the root of the subtree that $$$j$$$ is in for the set of good subtrees for node $$$i$$$. As there are at most $$$m$$$ representatives, we can find the contribution for each representative.

Let us fix an representative $$$r$$$. The $$$j$$$ that correspond to $$$r$$$ must be the subtree of $$$r$$$; this means that $$$i$$$ and $$$j$$$ are disjoint, and we can find $$$i$$$ by seeing if $$$i$$$ can reach $$$r$$$ but no ancestor of $$$r$$$. There are two methods to find this set. The first option is to run a transitive closure on the $$$r$$$ representatives, with bitset, and then process the representatives by dfs order to ensure that each representative is not reachable from the previous representative; we could also directly run a transitive closure on each representative and their fathers.

Once we find the sets corresponding to $$$i$$$ and $$$j$$$, we can find the desired contribution of said representative in $$$O(1)$$$ through prefix sums and PIE; therefore the total time complexity is $$$O((n+q)m)$$$.

This is a simpler version of the problem discussed here.

I was told that there are solutions based on Dirichlet convolution that should be faster, however I do not know the specifics of how a Dirichlet sieve would work here.