Hints: Zhily and Signpost

Do not think of the signposts as changing while you are walking in a complicated way. If the original query time is $m$, what is the time when you arrive at a fixed node $u$?

Answer to Hint 1: The time at node $u$ is always

$$ m + \mathrm{dist}(u), $$

where $\mathrm{dist}(u)$ is the sum of edge times on the path from the root to $u$.

This is independent of the choices made, because the tree has exactly one path from the root to $u$.

At an internal node $u$ with $d_u$ children, the chosen child is determined by

$$ (m + \mathrm{dist}(u)) \bmod d_u. $$

So every step only adds a modular condition on the original query value $m$.

Suppose some set of queries has reached node $u$, and all of them satisfy

$$ m \equiv r \pmod M. $$

If $d_u$ divides $M$, then all those queries have the same value modulo $d_u$. What does that mean for the next child?

Answer to Hint 4: If $d_u \mid M$, then the next child is fixed for the whole group:

$$ k = (r + \mathrm{dist}(u)) \bmod d_u. $$

So the entire group can be moved to child $s_{u,k}$ without inspecting its individual queries.

Now consider the other case: $d_u$ does not divide $M$. The old information $m \equiv r \pmod M$ is not enough to know $m \bmod d_u$.

What modulus should you refine to so that the child becomes determined?

Answer to Hint 6: Refine from $M$ to

$$ M' = \mathrm{lcm}(M, d_u). $$

For each query in the current group, compute $x = m \bmod M'$. Then the query belongs to the subgroup

$$ m \equiv x \pmod {M'}, $$

and its next child is

$$ (x + \mathrm{dist}(u)) \bmod d_u. $$

This suggests an offline algorithm: keep buckets of queries, where each bucket has a current node $u$ and a congruence condition $m \equiv r \pmod M$.

Move the whole bucket downward while the current node’s degree divides $M$. Split the bucket only when the degree does not divide $M$.

Why is the total work small?

When a bucket is split, the modulus changes from $M$ to $\mathrm{lcm}(M,d_u)$, which is a strict multiple of $M$. Therefore it grows by at least a factor of $2$.

Answer to Hint 9: Each query can be involved in only $O(\log 10^{18})$ splits, because after every split the modulus at least doubles.

The moves that do not split are also cheap globally: each tree node corresponds to at most one reachable congruence bucket, so these downward moves can be charged to nodes of the tree.

Implementation outline:

• compute $\mathrm{dist}(u)$ by one DFS or by processing nodes in increasing order;
• start with one bucket at the root, condition $m \equiv 0 \pmod 1$;
• process buckets from a queue;
• if a bucket reaches a leaf, assign that leaf to every query in it;
• otherwise either move it to one child, or split it by residues modulo the new lcm.