The obvious solution: store each node's parent, then jump up times. For each query, start at and follow the parent pointer times. This takes time per query. If (node is near a leaf, ancestor is the root), that is per query. With a million queries, that is a billion operations. Too slow.
You need a faster way to jump. The bottleneck: each jump moves you only one level up. What if you could skip multiple levels at once?