Idiot First Search

Research note: I cross-checked the recurrence against the official Codeforces editorial code (https://codeforces.com/blog/entry/151174), a short Nowcoder explanation (https://blog.nowcoder.net/n/4bbcf444bb15448b90355e50dc8f3bc9), and a public C++ solution (https://raw.githubusercontent.com/tar3q-az1z/Codeforces-solutions/main/2195E.cpp). They all reduce the problem to one subtree-completion DP and one ancestor accumulation pass. The explanation below is original and treats the supplied statement as canonical.

The trap is thinking the written letters create some awful global-state DP. They do not. Bob is doing DFS in the dumbest possible way, but it is still deterministic DFS: enter a clean internal node, visit the left subtree, visit the right subtree, erase the mark, then go upward.

Input detail first: the input describes vertices $1,2,\dots,n$. Vertex $0$ is only the outside root parent of vertex $1$, and is not listed. A pair 0 0 means the vertex is a leaf. So our represented tree is rooted at vertex $1$.

Define $down[v]$ as follows:

$down[v] = \text{number of moves until Bob moves from } v \text{ to } parent(v),$

assuming Bob starts at $v$ and every vertex in the subtree of $v$ is blank.

We also prove the stronger invariant: after those $down[v]$ moves, every vertex in the subtree of $v$ is blank again. This is what kills the scary state explosion.

If $v$ is a leaf, Bob immediately moves to its parent, so

$down[v]=1.$

The subtree had no letters before and still has no letters after, so the invariant holds.

Now suppose $v$ is internal, with children $l_v$ and $r_v$. Starting at a blank $v$:

• Bob writes L and moves to $l_v$: $1$ move.
• By induction, the left subtree finishes in $down[l_v]$ moves and is blank again. Bob is back at $v$, whose letter is still L.
• Bob overwrites it with R and moves to $r_v$: $1$ move.
• By induction, the right subtree finishes in $down[r_v]$ moves and is blank again. Bob is back at $v$, whose letter is now R.
• Bob erases R and moves to $parent(v)$: $1$ move.

So

$down[v]=down[l_v]+down[r_v]+3.$

The invariant also holds: both child subtrees are clean by induction, and $v$ erased its own mark before leaving. Nice. Bob accidentally wrote a reusable lemma. Wild times.

Now define $ans[v]$ as the required answer when Bob starts at vertex $v$ on the fully blank original tree.

After Bob starts at $v$ and spends $down[v]$ moves, he is at $parent(v)$. The subtree of $v$ is blank again, and no vertex outside that subtree was touched. Arriving at the parent does not write anything on it. Therefore the whole tree state is exactly the same as a fresh start at $parent(v)$.

Thus, with $ans[0]=0$,

$ans[v]=down[v]+ans[parent(v)].$

For vertex $1$, this says $ans[1]=down[1]$, because its parent is vertex $0$, where Bob has escaped.

Implementation:

1. Read children for vertices $1$ through $n$.
2. Build an iterative traversal order starting from vertex $1$.
3. Process that order in reverse to compute $down[v]$.
4. Process the order forward to propagate answers to children:

$ans[child]=ans[parent]+down[child].$

Everything is additive, so we can take modulo $10^9+7$ at every transition.

Edge cases:

• If $n=1$, vertex $1$ is a leaf, so the answer is $1$.
• A start from a right child is not special. Once Bob climbs to the parent, the parent is still blank, so Bob behaves exactly as if he started there from scratch.
• The tree can be very deep, so recursive DFS may stack-overflow. Use an explicit stack unless you enjoy debugging avoidable nonsense.

Complexity is $O(n)$ time and $O(n)$ memory per test case, and $O(\sum n)$ overall.