Where it runs
1. The problem
An HR tool keeps the company as a tree: employee i reports to employee parent[i], and the CEO's parent is -1. The tool has to answer one question again and again: who is the nearest common manager of two employees, that is, the first person both chains of reporting reach? And a related question: does employee X sit somewhere under manager M?
You can answer one such question by climbing both parent chains until they meet. That is O(depth) per question. On a deep tree with thousands of questions, it takes long.
The last lesson worked out blocks whose length is a power of two over an array in advance, so that a range question needed no walk over the range. The same idea works on a tree. For every node, work out in advance its ancestor 1 step up, 2 steps up, 4, 8 and so on. Then any climb up the tree is a few big jumps instead of steps one by one.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Tree problems that ask about ancestors or paths again and again, such as the k-th ancestor or the lowest common ancestor of two nodes. A jump table of 2^k ancestors answers each question in O(log n) after O(n log n) building.
Use the lesson's table and jump by each set bit of k, returning minus 1 when k is larger than the node's depth.
One question on one tree, so the plain recursion from lesson 78 is enough. Binary lifting gives the same answer and pays off only when the questions repeat.
Keep for each node the counts of the 26 edge weights on its path from the root. The path from u to v has counts(u) + counts(v) minus twice counts(LCA), and the answer is the path length minus the largest count.
Every player passes to one receiver, so build the jump table on receiver together with the sum of ids along each jump, and lift k steps from every start.