Editorial: Zhily and Signpost
For a query starting at time $m$, the time when we arrive at a node $u$ is always
$$ m + \mathrm{dist}(u), $$where $\mathrm{dist}(u)$ is the sum of edge lengths from the root to $u$.
This is true because the tree has a unique path from the root to any node. Therefore, if we ever reach node $u$, the elapsed travel time is fixed; it does not depend on the query in any other way.
So at an internal node $u$ with $d_u$ children, the chosen child is
$$ s_{u,(m+\mathrm{dist}(u)) \bmod d_u}. $$The whole process is a sequence of modular conditions on the original query value $m$.
At a node $u$, choosing a particular child means choosing a particular value of
$$ (m + \mathrm{dist}(u)) \bmod d_u. $$For example, suppose $u$ has $3$ children and we want to go to child number $1$ in zero-based order. Then we need
$$ (m + \mathrm{dist}(u)) \bmod 3 = 1. $$This is equivalent to
$$ m \equiv 1 - \mathrm{dist}(u) \pmod 3. $$So after deciding which child is taken at node $u$, we learn a congruence condition on the original start time $m$.
Along a root-to-node path, several such conditions must hold at once. For instance, we might know:
$$ m \equiv 2 \pmod 3, $$and later also need
$$ m \equiv 1 \pmod 4. $$Instead of storing all previous conditions separately, we combine them into one condition:
$$ m \equiv r \pmod M. $$Here:
- $M$ is the current period of the information we know about $m$;
- $r$ is the residue of all query times in this group modulo $M$.
So $m \equiv r \pmod M$ means that all possible query times in the group look like
$$ r,\ r+M,\ r+2M,\ r+3M,\ldots $$This is exactly what the bucket stores. It does not mean that all queries have the same value of $m$; it means they are indistinguishable by all signpost choices already made on the path to the current node.
We process the queries offline. A bucket stores:
- a node $u$;
- a modulus $M$ and residue $r$;
- all query indices in this bucket.
The bucket invariant is:
Every query in this bucket has reached node $u$, and its start time satisfies $m \equiv r \pmod M$.
Initially, all queries are in one bucket:
$$ u = 1,\qquad M = 1,\qquad r = 0. $$Now process one bucket at node $u$.
If $u$ is a leaf, all queries in the bucket have answer $u$.
Otherwise, let $d = d_u$.
At this point, to choose the next child we only need $m \bmod d$. The bucket already tells us $m \bmod M$. There are two cases.
If $d \mid M$, then all values in the bucket have the same residue modulo $d$:
$$ m \bmod d = r \bmod d. $$Therefore the next child is fixed for the entire bucket:
$$ k = (r + \mathrm{dist}(u)) \bmod d. $$We can move the whole bucket to child $s_{u,k}$ without looking at the individual queries.
For example, if the bucket says $m \equiv 5 \pmod {12}$ and the current node has $d=3$ children, then every such $m$ satisfies
$$ m \equiv 2 \pmod 3, $$because $12$ is a multiple of $3$. Therefore all queries in the bucket choose the same child.
If $d \nmid M$, the current congruence is not enough to determine $m \bmod d$.
For example, if the bucket says $m \equiv 1 \pmod 2$ and the current node has $d=3$ children, then possible values are
$$ 1,3,5,7,\ldots $$Modulo $3$, these are not all the same. They cycle through $1,0,2,1,\ldots$, so the bucket must be split.
Refine the modulus to
$$ M' = \mathrm{lcm}(M,d). $$For each query time $m$ in this bucket, compute
$$ x = m \bmod M'. $$Then this query belongs to the new congruence class
$$ m \equiv x \pmod {M'}, $$and its next child is
$$ k = (x + \mathrm{dist}(u)) \bmod d. $$Group the queries by the pair $(k,x)$ and create one new bucket for each nonempty group:
$$ u' = s_{u,k},\qquad M' = \mathrm{lcm}(M,d),\qquad r' = x. $$This new bucket has the same meaning as before, just with stronger information:
$$ m \equiv r' \pmod {M'}. $$Because $M'$ is a multiple of both $M$ and $d$, this one condition preserves the old path information and also determines the child at the current node.
Whenever we split a bucket, the modulus strictly increases:
$$ \mathrm{lcm}(M,d) > M. $$Since it is an integer multiple of $M$, it increases by at least a factor of $2$. Query times are at most $10^{18}$, so each query can participate in only $O(\log 10^{18})$ such splits.
The non-splitting moves are cheap globally. For a fixed tree node, the path from the root to it imposes a fixed system of congruences. If that system is consistent, it gives one residue class modulo the lcm of the degrees on the path; if it is inconsistent, no query reaches the node. Thus each tree node appears in at most one bucket during the whole process.
So all whole-bucket downward moves cost $O(n)$ total, and all splitting work costs
$$ O(q \log 10^{18}). $$Compute $\mathrm{dist}(u)$ first. Since parents satisfy $f_u < u$, this can be done in input order:
$$ \mathrm{dist}(u) = \mathrm{dist}(f_u) + l_u. $$Store children in increasing order. This already happens if we append node $u$ to the child list of $f_u$ while reading $u = 2,3,\ldots,n$.
Use a queue or stack of buckets. For each bucket:
- Move it downward while the current node is not a leaf and $d_u \mid M$.
- If it reaches a leaf, write that leaf as the answer for every query in the bucket.
- Otherwise compute $M'=\mathrm{lcm}(M,d_u)$, repartition the bucket’s queries by $m \bmod M'$ and the selected child, and push the resulting buckets.
The lcm can be maintained with 128-bit integers. It is also fine to cap it above $10^{18}$, because for all possible query times $m$, once $M > 10^{18}$ we have $m \bmod M = m$.
The total time is
$$ O(n + q \log 10^{18}), $$which is easily fast enough for the given limits.
The memory usage is $O(n+q)$, besides the storage used by temporary bucket groups.