Idiot First Search and Queries

Research note. I checked the official Codeforces problem page, the official Round 1080 editorial/code at https://codeforces.com/blog/entry/151174, and accepted-submission status evidence from Codeforces. The official prose for G is basically absent, so the proof below is derived from the statement and cross-checked against the official code idea. No source text is copied.

The key is to stop simulating Bob's tiny brain cell one move at a time. The letter states make every subtree behave like a deterministic tour.

For a vertex $v$, define $s_v$ as the number of moves from starting at $v$ with all relevant marks blank until Bob first moves from $v$ to its parent.

If $v$ is a leaf, Bob immediately moves to the parent, so $s_v=1$.

If $v$ has children $l$ and $r$, the behavior is forced:

1. at blank $v$, write L and move to $l$;
2. complete the whole tour of $l$ and return to $v$;
3. overwrite L to R and move to $r$;
4. complete the whole tour of $r$ and return to $v$;
5. erase R and move to the parent.

So

$s_v = s_l + s_r + 3$.

Now define $E_v$ as the list of vertices Bob is standing on after offsets $0,1,...,s_v-1$ during this local tour. Then:

• leaf: $E_v = [v]$;
• internal: $E_v = [v] + E_l + [v] + E_r + [v]$.

This is just an Euler tour with repeated internal vertices. Crucially, if we build this list for the whole tree rooted at vertex $1$, every $E_v$ is a contiguous segment starting at $tin_v$.

Next, we need total escape time. Let $T_v$ be the time to reach vertex $0$ when starting from $v$. Vertex $0$ itself is not stored in the input; it is only the parent of vertex $1$.

For vertex $1$:

$T_1 = s_1$.

For any other vertex $c$ with parent $p$:

$T_c = s_c + T_p$.

Why? After Bob finishes the local tour of $c$, he is at $p$, and every mark written inside $c$'s subtree has been erased again. Nothing magical leaks upward. Then the process continues exactly as if it had freshly started at $p$. This gives the concatenation:

$E_v, E_{parent(v)}, E_{parent(parent(v))}, ..., E_1$.

For a query $(v,k)$, suppose the current chunk is some ancestor $w$ of $v$. The number of moves spent before entering chunk $E_w$ is:

$T_v - T_w$.

So we need the highest ancestor $w$ such that:

$T_v - T_w <= k$.

Then the local offset inside $E_w$ is:

$off = k - (T_v - T_w)$,

and the answer is:

$euler[tin_w + off]$.

We find that ancestor with binary lifting. Since $n <= 300001$, 20 jump levels are enough.

A couple of edge cases:

• If $k=0$, the condition keeps $w=v$, offset is $0$, answer is $v$.
• If $v$ is a leaf, its local tour has length $1$, so after one move we jump to its parent chunk. Clean.
• The query guarantee $k<T_v$ means Bob never reaches vertex $0$, so the answer is always one of $1..n$.
• Do not modulo $T_v$. Problem E needed modulo; this one needs comparisons. Use 64-bit integers, because a skewed full binary tree can make $T_v$ quadratic-ish in $n$.

Precomputation:

1. Compute all $s_v$ bottom-up.
2. Build $T_v$, binary lifting parents, $tin_v$, and the Euler tour top-down.
3. Answer each query in $O(log n)$.

Complexity is $O(n log n + q log n)$ time and $O(n log n)$ memory per test case. The Euler array has length $s_1 = 2n-1$, so no giant nonsense hiding there.