Zhily and Signpost

Observation 1: the walk is really about congruences

The tree is just scenery. The real object is this:

If you are at node $u$ at time $t$, you go to child $s_{u,\, t \bmod d_u}.$

When starting from the root at time $m$, you reach node $u$ at time $m + \operatorname{dist}(u),$ where $\operatorname{dist}(u)$ is the total edge length from the root to $u$.

So to take the $i$-th child of $u$, the starting time must satisfy $m + \operatorname{dist}(u) \equiv i \pmod{d_u},$ that is $m \equiv i - \operatorname{dist}(u) \pmod{d_u}.$

That’s the whole game.

---

Observation 2: every reachable node corresponds to one residue class

For every node $u$, define $S_u$ as the set of starting times $m$ for which the walk visits $u$.

Claim: $S_u$ is either empty, or of the form $S_u = \{m \mid m \equiv a_u \pmod{M_u}\}.$

Why?

• For the root, obviously $S_1 = \{m \mid m \equiv 0 \pmod 1\}.$
• Suppose $u$ is the $i$-th child of $p$. To reach $u$, we must both:
  1. reach $p$, so $m \equiv a_p \pmod{M_p}$,
  2. choose child $i$ at $p$, so $m \equiv i - \operatorname{dist}(p) \pmod{d_p}.$

So $S_u$ is the intersection of two congruence classes. By CRT, that intersection is either empty or another single congruence class.

Boom. Each reachable node has exactly one pair $(a_u, M_u)$.

---

Observation 3: most "branching" nodes are lying to you

Suppose $u$ is reachable with class $m \equiv a \pmod M.$

If $d_u \mid M,$ then all such $m$ have the same value modulo $d_u$. Therefore $(m + \operatorname{dist}(u)) \bmod d_u$ is also fixed, so the chosen child is fixed.

So even if $u$ has 17 children, from the point of view of all valid starting times that reach $u$, only one child is possible.

Also, if $d_u=1$, it’s obviously deterministic.

That means we can contract chains of deterministic transitions. The only nodes we really care about are the ones where the reachable class still allows several different residues modulo $d_u$.

---

Observation 4: every real split at least doubles the modulus

Now suppose $u$ is reachable with class $m \equiv a \pmod M$, and $d_u \nmid M$. Then this node is a real split.

For a reachable child, the new modulus becomes $M' = \operatorname{lcm}(M, d_u) = M \cdot \frac{d_u}{\gcd(M,d_u)}.$

Because $d_u \nmid M$, we have $\frac{d_u}{\gcd(M,d_u)} \ge 2,$ so $M' \ge 2M.$

That’s the killer fact.

Starting from $M=1$, after at most about $60$ real splits, the modulus exceeds $10^{18}$. Since all queries satisfy $0 \le m \le 10^{18}$, once the modulus is bigger than $10^{18}$, that congruence class contains at most one possible query value.

From that point on, the process is fully deterministic for the query range. No more fancy math, just walk to the leaf.

So the effective branching depth is at most $\lfloor \log_2(10^{18}) \rfloor + 1 \le 60.$ That’s tiny. The big scary tree just collapsed.

---

Building the reduced tree

We recursively build states of the form:

• current original node $u$,
• a reachable class $m \equiv a \pmod M,$ with $M \le 10^{18}$.

Then we do this:

1. Skip deterministic stuff

While one of the following holds:

• $u$ is not a leaf and $d_u = 1$, or
• $d_u \mid M$,

we already know the unique child index: $j = (a + \operatorname{dist}(u)) \bmod d_u.$ So we just move to that child and continue with the same class $(a,M)$.

2. Stop if we hit a leaf

Then this state answers with that leaf.

3. Otherwise this is a real split

Here $d_u \nmid M$. For each child index $i$, we solve $m \equiv a \pmod M,$ $m \equiv i - \operatorname{dist}(u) \pmod{d_u}.$

• If there is no CRT solution, that child is unreachable.
• If the new modulus $M' = \operatorname{lcm}(M,d_u) \le 10^{18}$, we recurse with the child and the new class.
• If $M' > 10^{18}$, then there is at most one relevant query time left. Let $x$ be the smallest nonnegative CRT solution.
  • If $x > 10^{18}$, no query reaches that child.
  • Otherwise the only possible starting time is exactly $m=x$, so we just simulate the walk deterministically from there to the final leaf.

This creates a reduced tree consisting only of real split states plus terminal leaves.

Each original node is processed only once along its unique root path, so preprocessing stays linear-ish.

---

Answering queries

For a query $m$:

• start at the root state of the reduced tree,
• while the current state is a split at original node $u$:
  • compute $i = (m + \operatorname{dist}(u)) \bmod d_u,$
  • jump to the precomputed destination for child index $i$.

Eventually you land in a terminal leaf.

Since the reduced depth is at most about $60$, each query is answered in $O(60) = O(1)$ for all practical purposes.

---

Why this is correct

The correctness is basically three tiny facts glued together:

1. Reachable times for a node form one congruence class.
   Proven by induction and CRT.

2. If $d_u \mid M$, the next child is fixed.
   Because all times in that class are identical modulo $d_u$.

3. If $d_u \nmid M$, every reachable child refines the class to a strictly larger modulus.
   So the only genuine branching points are exactly the split states we keep.

The reduced tree preserves all possible query behaviors. Query traversal uses the exact same child rule $(m + \operatorname{dist}(u)) \bmod d_u,$ just skipping nodes where that rule is already predetermined.

So the leaf returned by the reduced tree is exactly the leaf of the original process. No magic, just less useless walking.

---

Complexity

Let $N$ be the total number of nodes in a test case and $Q$ the number of queries.

• Preprocessing / building the reduced tree: each reachable original node and edge is handled $O(1)$ times, plus CRT/gcd work.

  Complexity is $O(N \log C),$ where $C \le 10^{18}$, easily fast enough.

• Each query walks through at most about $60$ split states: $O(Q \log 10^{18}) = O(60Q).$

With the given limits, this is comfortably accepted.

Yeah, the problem looks like "tree simulation". It’s not. It’s a CRT automaton wearing a tree costume.