Ancestors k steps up
Some questions about a rooted tree look up toward the root: which vertex is 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 employees numbered 1 to . Employee 1 is the general director, and every other employee has a boss with a smaller number, so the bosses form a tree.
Answer queries. Each gives an employee and a number : print the boss levels above , or -1 if there is none.
The first line holds and , the second the bosses , and then come the queries, one per line.
Constraints
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 levels takes 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 simple steps a second, so this takes
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 has ancestors, so the table holds
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 tell us which ancestors to keep. Every is a sum of distinct powers of two, the ones its binary digits select:
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 up to . 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 is the vertex reached by following parent links times from ; for it is itself. If the climb would pass the root, there is none, written -1.
Build each jump from two half jumps
To build the table, we need a tree a little larger than the sample. We number its vertices from 0 and store it as a parent array, where entry is the parent of and -1 marks the root, vertex 0: parents = [-1, 0, 0, 1, 1, 3, 3, 5, 6, 7]. Vertex 9's parent is 7, 7's parent is 5 and 5's parent is 3, so the 3rd ancestor of 9 is 3.
Let's write up[j][v] for the vertex steps above , or -1 if is not that deep. Row 0 is the parent array itself, since . To fill the rows after it, we split each jump in half: a jump of steps is two jumps of steps, the first from and the second from wherever the first lands. So
Each row is built from the row before it in one pass. If the first half jump already returns -1, the entry must stay -1. In Python, up[j - 1][-1] would return the last entry of the row, which is a wrong ancestor; in C++ it would read outside the array.
The number of rows comes from the longest possible climb. No climb in an -vertex tree is longer than steps, and rows 0 to can make any climb shorter than steps, the lengths that fit in binary digits. The number of binary digits of is always enough, because it makes larger than , so the table needs
rows: 4 for our example, and 18 for 200,000 vertices. Python computes as n.bit_length() and C++ as bit_width(unsigned(n)).
The jump table for the example tree
| Jump | v = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 step | -1 | 0 | 0 | 1 | 1 | 3 | 3 | 5 | 6 | 7 |
| 2 steps | -1 | -1 | -1 | 0 | 0 | 1 | 1 | 3 | 3 | 5 |
| 4 steps | -1 | -1 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 1 |
| 8 steps | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
Each cell comes from the row above it. For example, up[1][9] reads up[0][9] = 7 and then up[0][7] = 5, so 2 steps above 9 is 5. The 8-step row is all -1, because the deepest vertex, 9, is only 5 steps below the root.
Climb k steps using the bits of k
With the table built, we climb steps from by reading the bits of from the lowest. Where bit is 1, we jump with row from the current vertex; where it is 0, we skip row . Let's try vertex 9 and . Bit 0 is 1, so we jump 1 step, from 9 to up[0][9] = 7. Bit 1 is 0, so we skip the 2-step row. Bit 2 is 1, so we jump 4 steps, from 7 to up[2][7] = 0. The answer is 0, after two jumps instead of five single steps:
Each jump starts from the vertex the previous jump reached, so the jumps add up to one climb of exactly steps. If a jump returns -1, the climb ran past the root, and the answer is -1. And if , the answer is -1 before we read the table at all: no vertex is or more steps below the root, and checking first keeps a large from reaching for a row the table does not have.
Step through the jumps
Let's watch the climb from a chosen vertex, with set by switching its bits. Each step handles one bit of , lowest first: a 1 bit jumps through the table cell it reads, which lights up, and a 0 bit skips its row. With from vertex 9, the climb runs off the top of the tree.
The widget's Common ancestor mode finds the lowest common ancestor of two vertices, the subject of the next part.
Jump table invariant
up[j][v] is the vertex exactly steps above , or -1. After the bits of below bit are handled, the current vertex is exactly as many steps above the start as those bits are worth.
The proof goes row by row. Row 0 is right by the definition of a parent. Suppose row is right. Then two of its jumps in a row climb
so row is right too, and by induction every row is. In a query each 1 bit adds its own power of two to the climb, so after the highest bit the walk has climbed exactly steps.
Answer the k-th ancestor queries
To turn this into a program, we first subtract 1 from every employee number, so the employees become 0 to and the director's parent is -1; the sample becomes [-1, 0, 0, 2, 2]. Then build makes the table, kth_ancestor climbs by the bits of , and the answer gets 1 added back unless it is -1.
input = sys.stdin.readline
def build(parents):
n = len(parents)
up = [parents[:]]
for j in range(1, n.bit_length()):
prev = up[j - 1]
up.append([-1 if half == -1 else prev[half] for half in prev])
return up
def kth_ancestor(up, v, k):
if k >= len(up[0]):
return -1
j = 0
while k and v != -1:
if k & 1:
v = up[j][v]
k >>= 1
j += 1
return v
n, q = map(int, input().split())
parents = [-1] + [e - 1 for e in map(int, input().split())]
up = build(parents)
answers = []
for _ in range(q):
x, k = map(int, input().split())
v = kth_ancestor(up, x - 1, k)
answers.append(-1 if v == -1 else v + 1)
print("\n".join(map(str, answers)))On the sample input the program prints 3, 1 and -1.
Let's follow the sample query (4, 2). It becomes kth_ancestor(up, 3, 2). Only bit 1 of is set, so the climb reads up[1][3] = 0, and the program prints employee 1.
Worked example
Trace the table and the queries
The trace builds the example's four rows and then answers a list of (vertex, ) queries bit by bit. On a chain of 12 vertices, climbing 11 steps from the bottom takes the jumps of , and a single vertex asked for its millionth ancestor gets -1 before any jump.
The first jump row stores each vertex’s direct parent. -1 means no ancestor. 10 vertices need 4 rows, one per binary digit of 10.
Change the example input
Current result: [3,0,3,-1]
Recall Why must the second jump start from the new vertex?
A 5-step climb from 9 is one step to 7, then four steps from 7. Reading both cells from 9 instead gives up[0][9] = 7 and up[2][9] = 1, and neither is 5 steps up. Every lookup continues the climb from the vertex the last jump reached.
What is the lowest common ancestor?
So far, the table has told us where one climb ends. It can also tell us where two climbs meet.
The company is the same as in Company Queries I: employees, employee 1 the director, and the boss of every other employee given on the second line.
Answer queries. Each gives two employees and : print their lowest common boss.
Constraints
Sample · Input
5 3 1 1 3 3 4 5 2 5 1 4
Output
3 1 1
In tree terms, we want the lowest common ancestor (LCA) of and : the deepest vertex that is an ancestor of both, where a vertex counts as its own ancestor. In the sample, employees 4 and 5 both report to 3, so their LCA is 3. The first boss that 2 and 5 share is the director, so (2, 5) prints 1. And (1, 4) prints 1, because the director is above 4 and is one of the pair.
The jump table finds the LCA in two stages. First, and may sit at different depths, so their climbs to the LCA have different lengths, and we even them out: we lift the deeper vertex, say , by steps with a -th ancestor query. If the two are now the same vertex, one was an ancestor of the other, and that vertex is the answer. Otherwise both are equally deep and below the LCA.
Second, both now need the same number of steps to reach the LCA, but we do not know that number. We try the rows from the largest down. If up[j][a] and up[j][b] differ, both jumps stay below the LCA, so we take them; if they agree, the jumps would land on the LCA or above it, so we skip. When the loop ends, and are children of the LCA, and the answer is up[0][a].
Find the LCA of 9 and 8
Let's run this on the example tree. Vertex 9 has depth 5 and vertex 8 has depth 4, so we lift 9 by step, to 7. From 7 and 8, the 8-step jumps both give -1 and the 4-step jumps both give 0, so we skip them. The 2-step jumps give 3 and 3, so we skip again. The 1-step jumps give 5 and 6, which differ, so we move to 5 and 6. Their parent, 3, is the LCA.
The rows must go from largest to smallest. After the same number of steps up from and from , the two ancestors differ while they are below the LCA and agree from the LCA up. So the climb from to the child of the LCA has a fixed length , and a jump of lands on two different ancestors exactly when is at most what is left of .
Taking the rows largest first writes in binary, as a -th ancestor query does. Smallest first tries each row once in the wrong order: with it takes the 1-step jump, the 2-step jump no longer fits, and the climb ends one step short.
Answer the LCA queries
build and kth_ancestor are the same as in Company Queries I. The depths fill in increasing employee order, which works because every boss has a smaller number than the employee.
input = sys.stdin.readline
def build(parents):
n = len(parents)
up = [parents[:]]
for j in range(1, n.bit_length()):
prev = up[j - 1]
up.append([-1 if half == -1 else prev[half] for half in prev])
return up
def kth_ancestor(up, v, k):
if k >= len(up[0]):
return -1
j = 0
while k and v != -1:
if k & 1:
v = up[j][v]
k >>= 1
j += 1
return v
def lca(up, depth, a, b):
if depth[a] < depth[b]:
a, b = b, a
a = kth_ancestor(up, a, depth[a] - depth[b])
if a == b:
return a
for j in reversed(range(len(up))):
if up[j][a] != up[j][b]:
a, b = up[j][a], up[j][b]
return up[0][a]
n, q = map(int, input().split())
parents = [-1] + [e - 1 for e in map(int, input().split())]
depth = [0] * n
for v in range(1, n):
depth[v] = depth[parents[v]] + 1
up = build(parents)
answers = []
for _ in range(q):
a, b = map(int, input().split())
answers.append(lca(up, depth, a - 1, b - 1) + 1)
print("\n".join(map(str, answers)))On the sample input the program prints 3, 1 and 1.
Find the distance between two vertices
With an LCA query in , we can also find the length of any path in a tree.
You get a tree of nodes numbered 1 to , as edges.
Answer queries. Each gives two nodes and : print the number of edges on the path between them.
Constraints
Sample · Input
5 3 1 2 1 3 3 4 3 5 1 3 2 5 1 4
Output
1 3 2
We can root the tree anywhere, say at node 1. The path from to then climbs to their LCA and descends to . The climb has edges and the descent , so the whole path has
Let's check the sample query (2, 5). Node 2 has depth 1, node 5 has depth 2, and their LCA is node 1, at depth 0, so
the path 2, 1, 3, 5. This time the input gives edges, not parents, and a parent need not have a smaller number than its child. So we first search from the root to find each parent and depth: every neighbor of a vertex except its parent is one of its children. After that, build and lca work unchanged.
Deeper read: the full Distance Queries program
input = sys.stdin.readline
def build(parents):
n = len(parents)
up = [parents[:]]
for j in range(1, n.bit_length()):
prev = up[j - 1]
up.append([-1 if half == -1 else prev[half] for half in prev])
return up
def kth_ancestor(up, v, k):
if k >= len(up[0]):
return -1
j = 0
while k and v != -1:
if k & 1:
v = up[j][v]
k >>= 1
j += 1
return v
def lca(up, depth, a, b):
if depth[a] < depth[b]:
a, b = b, a
a = kth_ancestor(up, a, depth[a] - depth[b])
if a == b:
return a
for j in reversed(range(len(up))):
if up[j][a] != up[j][b]:
a, b = up[j][a], up[j][b]
return up[0][a]
n, q = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n - 1):
a, b = map(int, input().split())
adj[a - 1].append(b - 1)
adj[b - 1].append(a - 1)
parents, depth = [-1] * n, [0] * n
stack = [0]
while stack:
v = stack.pop()
for u in adj[v]:
if u != parents[v]:
parents[u] = v
depth[u] = depth[v] + 1
stack.append(u)
up = build(parents)
answers = []
for _ in range(q):
a, b = map(int, input().split())
c = lca(up, depth, a - 1, b - 1)
answers.append(depth[a - 1] + depth[b - 1] - 2 * depth[c])
print("\n".join(map(str, answers)))On the sample input the program prints 1, 3 and 2.
Repeat a move up to a billion times
Nothing in the table needs a tree: each entry follows one link times. In the next problem, the links are teleporters, and they can form cycles.
There are planets numbered 1 to , and planet has a teleporter to planet , possibly itself.
Answer queries. Each gives a start planet and a number : print the planet you reach after using teleporters in a row.
Constraints
Sample · Input
4 3 2 1 1 4 1 2 3 4 4 1
Output
1 2 4
Let's read the sample. The query (1, 2) goes 1, 2, 1 and prints 1; (3, 4) goes 3, 1, 2, 1, 2 and prints 2; and (4, 1) stays on planet 4, whose teleporter leads to itself.
A graph where every vertex has exactly one outgoing edge is called a functional graph, because it is a function from vertices to vertices. Each planet has one next planet, just as each tree vertex has one parent, so the same table works: row 0 is the teleporter list and up[j][v] = up[j - 1][up[j - 1][v]]. Every planet has a next planet, so the table has no -1 entries.
This time the number of rows has to come from . A walk can go around a cycle forever, as planets 1 and 2 do, so the number of moves is not limited by the number of planets. The rows must cover every up to , which takes 30 rows, because
Answer the teleporter queries
input = sys.stdin.readline
n, q = map(int, input().split())
up = [[int(t) - 1 for t in input().split()]]
for j in range(1, 30):
prev = up[j - 1]
up.append([prev[p] for p in prev])
answers = []
for _ in range(q):
x, k = map(int, input().split())
v, j = x - 1, 0
while k:
if k & 1:
v = up[j][v]
k >>= 1
j += 1
answers.append(v + 1)
print("\n".join(map(str, answers)))On the sample input the program prints 1, 2 and 4.
The table holds
and each query makes at most 30 jumps, where teleporting one step at a time could take a billion.
How long building and querying take
- Build a tree table
time n.bit_length()rows of entries, two lookups each.- Memory
- 3.6 million entries for 200,000 vertices; when reaches .
- One k-th ancestor or LCA query
- One jump per bit of , or a lift plus one pass down the rows.
All of this assumes the parents never change. A new leaf is cheap to add, because each of its entries depends only on ancestors that already have theirs, so filling its column takes . Changing an existing parent can invalidate the entries of every vertex below it, so the table has to be rebuilt.
Common binary lifting mistakes
Sizing the table with
int(math.log2(n))rows.- Where it breaks
- On a chain of 13 vertices it gives rows: 1, 2 and 4 steps. The query
(12, 12)needs , and readingup[3]raisesIndexError. - The fix
- Use
n.bit_length()rows: 4 for .
Filling a row with
prev[prev[v]]without checking for -1.- Where it breaks
- On the example
up[1][0]becomes7instead of-1, and the query(3, 4)returns7, a vertex below 3. - The fix
- Keep -1 as -1:
-1 if half == -1 else prev[half].
Trying the LCA jumps from the smallest up.
- Where it breaks
- With two branches of three vertices,
parents = [-1, 0, 0, 1, 2, 3, 4], and the pair 5 and 6, the 1-step jumps give 3 and 4 and both move. The 2-step jumps then both give 0 and are skipped, so the answer comes out as1, which is not above 6. The LCA is0. - The fix
- Go from the largest row down.
Skipping the check after lifting to the same depth.
- Where it breaks
- For 9 and 3, lifting 9 by lands on 3 itself. Without the check, the loop takes no jumps and returns
1, the parent of 3, instead of3. - The fix
- Return at once when the two are the same vertex after the lift.
Further reading
- USACO Guide, PlatinumBinary Jumping(opens in a new tab)
Works through Company Queries I and II and Distance Queries, then lists harder ones.
- cp-algorithmsLowest Common Ancestor - Binary Lifting(opens in a new tab)
Builds the table during a DFS and tests ancestry by entry and exit times instead of lifting by depth.
- Antti Laaksonen, chapters 16 and 18 (PDF)Competitive Programmer’s Handbook(opens in a new tab)
Section 16.3 doubles the moves of a successor graph; chapter 18 covers -th ancestors, the LCA and tree distances.
- OI Wiki, in Chinese最近公共祖先 (Lowest common ancestor)(opens in a new tab)
The 倍增 (doubling) section is this lesson’s method; other sections use Tarjan’s offline algorithm or range minimums over an Euler sequence.