Red-Blue Graph
Contest: Codeforces Global Round 6
Difficulty rating: 3400
Tags: dp, graphs, math, matrices, meet-in-the-middle

There is a directed graph on $$$n$$$ vertices numbered $$$1$$$ through $$$n$$$ where each vertex (except $$$n$$$) has two outgoing arcs, red and blue. At any point in time, exactly one of the arcs is active for each vertex. Initially, all blue arcs are active and there is a token located at vertex $$$1$$$. In one second, the vertex with token first switches its active arcs — the inactive arc becomes active and vice versa. Then, the token is moved along the active arc. When the token reaches the vertex $$$n$$$, it stops. It is guaranteed that $$$n$$$ is reachable via arcs from every vertex.

You are given $$$q$$$ queries. Each query contains a state of the graph — a pair $$$(v, s)$$$ of the following form:

- $$$v$$$ is the vertex where the token is currently located;
- $$$s$$$ is a string consisting of $$$n - 1$$$ characters. The $$$i$$$-th character corresponds to the color of the active edge leading from the $$$i$$$-th vertex (the character is 'R' if red arc is active, otherwise the character is 'B').

For each query, determine whether the given state is reachable from the initial state and the first time this configuration appears. Note that the two operations (change active arc and traverse it) are atomic — a state is not considered reached if it appears after changing the active arc but before traversing it.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 58$$$) — the number of vertices.

$$$n-1$$$ lines follow, $$$i$$$-th of contains two space separated integers $$$b_i$$$ and $$$r_i$$$ ($$$1 \leq b_i, r_i \leq n$$$) representing a blue arc $$$(i, b_i)$$$ and red arc $$$(i, r_i)$$$, respectively. It is guaranteed that vertex $$$n$$$ is reachable from every vertex.

The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 5000$$$) — the number of queries.

Then $$$q$$$ lines with queries follow. The $$$j$$$-th of these lines contains an integer $$$v$$$ ($$$1 \leq v < n$$$) and a string $$$s$$$ of length $$$n-1$$$ consiting only of characters 'R' and 'B'. The $$$i$$$-th of these characters is 'R' if the red arc going from $$$i$$$ is active and 'B' otherwise.

Output format:
Output $$$q$$$ lines, each containing answer to a single query.

If the state in the $$$i$$$-th query is unreachable, output the integer $$$-1$$$. Otherwise, output $$$t_i$$$ — the first time when the state appears (measured in seconds, starting from the initial state of the graph which appears in time $$$0$$$).

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
The graph in the first example is depticed in the figure below.

The first $$$19$$$ queries denote the journey of the token. On the $$$19$$$-th move the token would reach the vertex $$$6$$$. The last two queries show states that are unreachable.

Example input:
6
2 1
5 5
2 1
6 3
4 3
21
1 BBBBB
1 RBBBB
2 BBBBB
5 BRBBB
3 BRBBR
1 BRRBR
1 RRRBR
2 BRRBR
5 BBRBR
4 BBRBB
3 BBRRB
2 BBBRB
5 BRBRB
3 BRBRR
1 BRRRR
1 RRRRR
2 BRRRR
5 BBRRR
4 BBRRB
2 BRBBB
4 BRBBR

Example output:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-1
-1

Editorial:
Consider a fixed query $$$\{s_i\}_{i=1}^{n-1}$$$ and $$$v$$$.
Let $$$x_i$$$ be the number of times the red arc from $$$i$$$ was traversed, and $$$y_i$$$ the number of times the blue arc was traversed. The answer for a given query, should the $$$x_i$$$ and $$$y_i$$$ exist, is the sum of all of them. Let's try to find these values.
When the blue arc going from $$$i$$$ is active, we have $$$x_i = y_i$$$. Otherwise, $$$x_i = y_i + 1$$$. In both cases
$$$$$$x_i = y_i + [s_i = \text{'R'}]\,.$$$$$$
Let's denote $$$B_i$$$ the set of blue arcs going to $$$i$$$, and $$$R_i$$$ the set of red arcs going to $$$i$$$. For every vertex other than $$$1$$$ and the current vertex $$$v$$$, the sum of traversals of incoming edges must equal the sum of traversals of outgoing edges. For the current vertex, the sum of incoming traversals is one more than the outgoing, and for vertex $$$1$$$ it is the opposite. This gives us
$$$$$$\sum_{r \in R_i} x_r + \sum_{b \in B_i} y_b + [ i = 1 ] = x_i + y_i + [ i = v ]\,.$$$$$$
Substituting the $$$y$$$s and rearranging yields:
$$$$$$2x_i - \sum_{r \in R_i} x_r - \sum_{b \in B_i} x_b = [ s_i = \text{'R'} ] - \sum_{b \in B_i} [s_b = \text{'R'}] + [ i = 1] - [ i = v ]\,.$$$$$$
Consider this equality for each $$$i$$$ from $$$1$$$ to $$$n-1$$$. We have $$$n-1$$$ equalities for $$$n-1$$$ unknowns, written in matrix form $$$Ax = z$$$. The value of $$$A$$$ does not depend on the actual query – it is determined by the structure of the graph. Let's look at the matrix in more detail.
On the main diagonal, each value is $$$2$$$ – because each vertex has outdegree $$$2$$$. Then there are some negative values for incoming edges. Those values are either $$$-1$$$, or $$$-2$$$ when both the red and blue edge have the same endpoint. In each column, the sum of negative entries is between $$$0$$$ and $$$-2$$$, because each $$$-1$$$ corresponds to and outgoing edge, and because some of the edges may end in $$$n$$$, for which we don't have equation.
This combined yields an important observation: the matrix $$$A$$$ is irreducibly diagonally dominant. That is, in each column it holds $$$|a_{ii}| \geq \sum_{i\neq j}|a_{ij}|$$$, and there is at least one column for which there is strict inequality (because vertex $$$n$$$ is reachable). An interesting property of such matrix is that it is non-singular. For every right side $$$z$$$ there is thus exactly one solution for $$$x$$$.
There are $$$2^{n-1} \cdot (n - 1)$$$ possible queries, and each of them corresponds to some pair of vectors $$$(x, y)$$$. Clearly, every reachable state corresponds to exactly one pair that describes the process that led to this state. However, it is evident that there are input graphs in which the target vertex is reached in fewer moves, hence some $$$(x, y)$$$ pairs must correspond to invalid states. Let's look at which states are invalid.
First, every element of $$$x$$$ must be non-negative and integer. Consider a graph on three vertices, where each arc, red or blue, goes to the vertex with higher ID ($$$1 \rightarrow 2$$$ and $$$2 \rightarrow 3$$$), $$$v = 2$$$ and $$$s = \text{"BB"}$$$. The solution of this linear system is $$$x = \left(\frac{1}{2}, 0\right)$$$. This is clearly not a valid state.
There is one more situation that is invalid. Consider again a graph on three vertices where each red arc goes to the vertex with higher ID as before, but each blue arc is a loop. In this graph, the token moves to the last vertex in two moves, making both red edges active in the process. For query $$$v = 2$$$ and $$$s = \text{"RR"}$$$, we get a solution $$$x = \left(1, 0\right)$$$ and $$$y = \left(1, 0\right)$$$. This is not a valid state. The reason for this is the fact that the active arc from $$$i$$$ speaks truth about a simple fact – where did the token go the last time it left vertex $$$i$$$. The active edge in vertex $$$1$$$ is blue, which leads to itself, meaning that the token never left the vertex. But this is a contradiction, because we know it is in vertex $$$2$$$. This condition can be phrased as follows:
For every vertex that had the token at least once, the vertex containing the token must be reachable via the active arcs.
These two conditions are in fact necessary and sufficient.
Let's summarise what we have so far:
1. Build a system of linear equations and solve for $$$x$$$.
2. Check whether all $$$x$$$ are non-negative and integer.
3. Verify that the current vertex is reachable from all visited vertices using active edges.
4. If both conditions are true, calculate $$$y$$$ and sum all $$$x$$$ and $$$y$$$ to get the answer. Otherwise, the answer is negative.
There are some technical details left to be solved.
Firstly, as we already noticed, the matrix $$$A$$$ doesn't depend on the actual query, only on the graph structure. We can thus precompute its inverse and solve each query as a matrix vector implementation, reducing time per query from $$$\mathcal O(n^3)$$$ to $$$\mathcal O(n^2)$$$.
Secondly, how do we compute $$$x$$$ precisely to check whether they are integers? There are two ways – either we use exact fractions with big integers, or compute everything in modular arithmetic and verify the solution on integers. Since $$$128$$$-bit integers are not a thing on codeforces, we either use Schrage's method for the modular multiplication, or use two moduli and Chinese remainder theorem.
The total complexity is $$$\mathcal O(n^3 + q \cdot n^2)$$$.