Cry Me a River

We need answer a changing game on a DAG. The nasty part is that the set of red vertices grows over time, so a plain DP per query would be very dead: $O(q(n+m))$ is not passing anything except maybe a vibe check.

The good news: painting nodes red only makes Cry's life worse. That monotonicity lets us process every state at most once.

Game DP with turns

There are really two states per vertex:

• $C_u$: Cry wins if the token is at $u$ and it is Cry's turn.
• $R_u$: Cry wins if the token is at $u$ and it is River's turn.

Terminal rules:

• If $u$ is red, River wins immediately, so $C_u = R_u = \text{false}$.
• If $u$ is a blue sink, Cry wins immediately, so $C_u = R_u = \text{true}$.

For a blue non-sink vertex:

$$C_u = \bigvee_{u \to v} R_v$$

Cry chooses the move, so he only needs one child that is good for him.

$$R_u = \bigwedge_{u \to v} C_v$$

River chooses the move, so Cry wins only if every possible River move still wins for Cry.

Queries of type $2u$ ask for $C_u$ under the current red set.

What changes when a node becomes red?

When vertex $u$ is painted red, both $C_u$ and $R_u$ become losing for Cry. Then this can affect its parents:

• If $C_v$ becomes losing, then for every parent $p$ with edge $p \to v$, $R_p$ becomes losing, because River can move from $p$ to $v$ and make Cry lose.
• If $R_v$ becomes losing, then for every parent $p$, one of Cry's options from $p$ is now bad. This does not necessarily make $C_p$ losing immediately. $C_p$ becomes losing only when all children $v$ have losing $R_v$.

That second condition is where a counter comes in.

Let:

$$\text{badRcnt}[u] = \#\{v : u \to v \text{ and } R_v \text{ is losing}\}$$

Then $C_u$ becomes losing exactly when:

$$\text{badRcnt}[u] = \text{outdegree}(u)$$

with one important detail: do not mark sinks losing from this rule. A blue sink is an immediate win for Cry. It only loses if it itself is painted red.

Why this is fast

Each of the $2n$ states, $C_u$ and $R_u$, can switch from winning to losing at most once. Every time a state switches, we scan reverse edges of that vertex. So the total work over all updates is $O(n+m)$, plus $O(1)$ per query.

No topological sorting is even needed. The DAG guarantees the game makes sense, but the propagation itself only relies on monotone state changes.

Propagation rules

Maintain:

• loseC[u]: whether $C_u$ is losing for Cry.
• loseR[u]: whether $R_u$ is losing for Cry.
• badRcnt[u]: number of outgoing children with loseR[child] = true.
• reverse adjacency, so we can update parents.

When a vertex becomes red, call markC(u) and markR(u).

When markC(v) happens:

• For every parent $p$ of $v$, call markR(p).

Reason: River at $p$ can choose $v$, and then Cry loses.

When markR(v) happens:

• For every parent $p$ of $v$, increment badRcnt[p].
• If badRcnt[p] == outdegree[p], call markC(p).

Reason: Cry at $p$ has no safe move left.

Because markC and markR ignore states already marked losing, every edge contributes only a constant number of times. Clean, brutal, done.