Trees and recursion 0/36

Lesson 6 of 6 Advanced

Binary lifting: ancestor queries with jump tables

Store ancestors 1, 2, 4, 8 and more steps up to answer k-th ancestor, LCA and distance queries in O(log n) jumps, and repeat a move a billion times.

3,224 words · 15 min read

Part 1 of 8 Binary lifting

Ancestors k steps up

Some questions about a rooted tree look up toward the root: which vertex is kk steps above a given one, and where the paths from two vertices up to the root first meet. One table of ancestors answers both. Company Queries I asks the first question.

A company has nn employees numbered 1 to nn. Employee 1 is the general director, and every other employee ii has a boss eie_i with a smaller number, so the bosses form a tree.

Answer qq queries. Each gives an employee xx and a number kk: print the boss kk levels above xx, or -1 if there is none.

The first line holds nn and qq, the second the bosses e2,…,ene_2, \dots, e_n, and then come the qq queries, one per line.

Constraints

  • 1≤n,q≤2⋅1051 \le n, q \le 2 \cdot 10^5
  • 1≤ei≤i−11 \le e_i \le i - 1
  • 1≤x≤n1 \le x \le n
  • 1≤k≤n1 \le k \le n

Sample · Input

5 3
1 1 3 3
4 1
4 2
4 3

Output

3
1
-1

Let's read the sample first. Employees 2 and 3 report to the director, and 4 and 5 report to 3. From employee 4, one level up is 3 and two levels up is 1. Three levels up would be above the director, so the last query prints -1.

Following one boss at a time, a query that climbs kk levels takes kk steps. The worst case is one chain of 200,000 employees, with each of 200,000 queries climbing from its bottom to its top. A judge runs roughly 10810^8 simple steps a second, so this takes

2×105×2×105=4×1010 steps4×1010÷108 steps a second≈400 seconds.\begin{aligned} 2 \times 10^5 \times 2 \times 10^5 &= 4 \times 10^{10} \text{ steps} \\ 4 \times 10^{10} \div 10^8 \text{ steps a second} &\approx 400 \text{ seconds.} \end{aligned}

That is 400 times the one-second limit. At the other extreme, we could store every ancestor of every vertex and answer each query with one lookup. On the chain, though, the vertex at depth dd has dd ancestors, so the table holds

0+1+⋯+(n−1)≈n22=2×1010 entries.0 + 1 + \dots + (n - 1) \approx \frac{n^2}{2} = 2 \times 10^{10} \text{ entries.}

At 4 bytes an entry, that is 80 GB, and the problem allows 512 MB. We need something in between: a small table per vertex and a few steps per query. The binary digits of kk tell us which ancestors to keep. Every kk is a sum of distinct powers of two, the ones its binary digits select:

5=1012=4+113=11012=8+4+1\begin{aligned} 5 &= 101_2 = 4 + 1 \\ 13 &= 1101_2 = 8 + 4 + 1 \end{aligned}

Suppose every vertex stores only its ancestors 1, 2, 4, 8 and so on steps up. Then a climb of 13 steps is three stored jumps, of 8, 4 and 1 steps, each starting where the one before it landed. A climb takes one stored jump for each 1 bit of its length. This is binary lifting. On the chain of 200,000 employees, no climb is longer than 199,999 steps, a number with 18 binary digits, so each vertex keeps at most 18 ancestors, at distances 202^0 up to 2172^{17}. That is 3.6 million entries, about 14 MB at 4 bytes each, and a query makes at most 18 jumps.

Definition

The k-th ancestor of a vertex vv is the vertex reached by following parent links kk times from vv; for k=0k = 0 it is vv itself. If the climb would pass the root, there is none, written -1.