SyntaxPilot
Courses/Competitive Programming/Lesson 53
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 53 of 90

LCA with binary lifting

queued

These are the notes for Competitive Programming episode 53. The lowest common ancestor (LCA) of two vertices of a rooted tree is the closest vertex that is an ancestor of both: the place where their two lines up to the root first meet. Family Register asks for it 2 · 10^5 times: climbing one generation at a time is correct but Time Limit Exceeded on a line of 2 · 10^5 generations. A register that also notes who is 2, 4, 8, 16 … generations up gives the jump table up[k][v] and binary lifting: lift by the binary digits of the depth gap, then jump both people together while they stay different. The first version forgets that one person can be the other's ancestor and prints 2 1 2 3 where 2 1 4 7 is right; with LOG = 17 the maximum test prints 800000 where 600000 is right, because 2^17 < 2 · 10^5. Courier Distance uses dist[u] + dist[v] − 2 · dist[lca]. Message Relay finds the k-th person on a route; counting the way down from the wrong end prints 2 2 3 4 where 2 9 3 8 is right. Two stress tests pass. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

In some pilgrimage towns, family priests keep family registers that go back many generations: every entry names a person and their father or mother. To find who was 13 generations above you, you could look up your parent, then their parent, thirteen look-ups. Now imagine that each entry also notes who is 2, 4, 8 and 16 generations up. Writing those notes takes some work once, but afterwards 13 generations is just 8 + 4 + 1: three look-ups. That is binary lifting: the notes are the jump table, and the look-ups follow the binary digits of 13 (1101).

Two cousins asking "where do our family lines meet?" first climb to the same generation, then keep making the biggest jumps that still land them on different people. When no jump is possible any more, they stand just below the meeting point, and the answer is one step up.

Problem A1 · Family Register

(Written for this course, in the style of a Codeforces Div. 2 problem.)

A family register lists n people. Person 1 is the founder; for every other person v (2 ≤ v ≤ n) it names their parent p_v. Answer q questions: for two people u and v, print the closest person who is an ancestor of both. A person counts as their own ancestor.

  • Input: n q (1 ≤ n, q ≤ 2 · 10^5), then p_2 … p_n, then q lines u v.
  • Output: one line per question.
9 4
1 1 2 2 3 3 4 5
8 9
8 6
4 8
7 7
Question Answer Why
8 9 2 8 → 4 → 2 and 9 → 5 → 2
8 6 1 different sides of the founder
4 8 4 4 is 8's parent, and an ancestor of itself
7 7 7 the same person

The sample family:

            1
        /       \
       2         3
     /   \     /   \
    4     5   6      7
    |     |
    8     9

The depth of a person is how many generations they are below the founder (depth(1) = 0, depth(8) = 3). The answer is called the lowest common ancestor: "lowest" means deepest, closest to u and v.

The obvious attempt: climb one generation at a time (TLE)

A BFS from the founder gives every depth (parents are always reached before their children). Then climb lifts the deeper person until both are at the same depth, and steps both up together until they are the same person.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, par[200001], dep[200001];
vector<int> ch[200001];                  // children

void depths() {                          // BFS from the founder
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
}

int climb(int u, int v) {                // one generation at a time
    while (dep[u] > dep[v]) u = par[u];
    while (dep[v] > dep[u]) v = par[v];
    while (u != v) u = par[u], v = par[v];
    return u;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int v = 2; v <= n; v++) {
        cin >> par[v];
        ch[par[v]].push_back(v);
    }
    depths();
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << climb(u, v) << "\n";
    }
}
2
1
4
7

Correct. The worst case is one long line: people 1, 2, …, 199 999 each the parent of the next, plus person 200 000 as a second child of person 3. Every question pairs someone near the bottom of the line with person 200 000, so every answer is 3.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, par[200001], dep[200001];
vector<int> ch[200001];                  // children

void depths() {                          // BFS from the founder
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
}

int climb(int u, int v) {                // one generation at a time
    while (dep[u] > dep[v]) u = par[u];
    while (dep[v] > dep[u]) v = par[v];
    while (u != v) u = par[u], v = par[v];
    return u;
}

int main() {
    n = 200000;                          // a long line, plus one child of 3
    for (int v = 2; v <= n; v++) {
        par[v] = v < n ? v - 1 : 3;
        ch[par[v]].push_back(v);
    }
    depths();
    ll sum = 0;
    for (int i = 0; i < 200000; i++)     // 2·10^5 deep queries
        sum += climb(n - 1 - i % 1000, n);
    cout << sum << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)

Each question climbs about 2 · 10^5 steps; 2 · 10^5 questions make about 4 · 10^10 steps. The time limit allows roughly 10^8 to 10^9 simple steps per second.

The jump table

Let up[k][v] be the person 2^k generations above v (and the founder if there is nobody that high). Row 0 is just the parent. Every other row comes from the one before it:

up[k][v] = up[k − 1][ up[k − 1][v] ]      // 2^k up = 2^(k−1) up, then 2^(k−1) up again

Filling LOG rows of n entries takes O(n log n). To jump d generations up, write d in binary and make one jump for every 1 bit: 13 = 8 + 4 + 1 = 1101₂, so three jumps.

person 14 → 8 up → person 6 → 4 up → person 2 → 1 up → person 1      (13 generations, 3 look-ups)

The two phases of lca(u, v)

  1. Lift. Make u the deeper one and jump it up by diff = dep[u] − dep[v], using the bits of diff. Now both are at the same depth.
  2. Check. If u == v now, v was an ancestor of u: return it.
  3. Jump together. For k from LOG − 1 down to 0: if up[k][u] != up[k][v], jump both. An equal answer could be the meeting point or somewhere above it, so we never jump when they are equal. Because we only jump while they differ, we end exactly one generation below the meeting point.
  4. Answer up[0][u].

Trace for (8, 9): same depth already. k = 1: up[1][8] = 2 and up[1][9] = 2, equal, no jump. k = 0: up[0][8] = 4 and up[0][9] = 5, different, jump: u = 4, v = 5. Answer up[0][4] = 2.

Bug 1: forgetting "v was an ancestor"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 17;
int n, up[LOG][200001], dep[200001];
vector<int> ch[200001];

void build() {
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
    up[0][1] = 1;                        // above the founder: the founder
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];   // 2^k up = 2^(k-1) up, twice
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if (diff >> k & 1) u = up[k][u];    // lift u to v's depth
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int v = 2; v <= n; v++) {
        cin >> up[0][v];
        ch[up[0][v]].push_back(v);
    }
    build();
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
}
2
1
2
3

For (4, 8), lifting 8 by one generation gives 4, so u == v. The jump loop never jumps (every pair of jumps is equal) and the function returns the parent of 4, which is 2. For (7, 7) it returns 3. The fix is the one line if (u == v) return u;.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 17;
int n, up[LOG][200001], dep[200001];
vector<int> ch[200001];

void build() {
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
    up[0][1] = 1;                        // above the founder: the founder
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];   // 2^k up = 2^(k-1) up, twice
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if (diff >> k & 1) u = up[k][u];    // lift u to v's depth
    if (u == v) return u;                // v was an ancestor of u
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int v = 2; v <= n; v++) {
        cin >> up[0][v];
        ch[up[0][v]].push_back(v);
    }
    build();
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
}
2
1
4
7
1

Bug 2: LOG one level short

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 17;
int n, up[LOG][200001], dep[200001];
vector<int> ch[200001];

void build() {
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
    up[0][1] = 1;                        // above the founder: the founder
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];   // 2^k up = 2^(k-1) up, twice
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if (diff >> k & 1) u = up[k][u];    // lift u to v's depth
    if (u == v) return u;                // v was an ancestor of u
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

int main() {
    n = 200000;                          // a long line, plus one child of 3
    for (int v = 2; v <= n; v++) {
        up[0][v] = v < n ? v - 1 : 3;
        ch[up[0][v]].push_back(v);
    }
    build();
    ll sum = 0;
    for (int i = 0; i < 200000; i++)     // 2·10^5 deep queries
        sum += lca(n - 1 - i % 1000, n);
    cout << sum << "\n";
}
800000

Every answer came out as 4 instead of 3. With LOG = 17 the biggest climb the table can make is 2^17 − 1 = 131 071 generations, but the depth gap here is almost 2 · 10^5. The lift falls short, and the jump phase cannot climb far enough either, so the function answers a person below the real meeting point. The rule: 2^LOG must be bigger than the largest depth (n − 1 at most). For n = 2 · 10^5, 2^18 = 262 144 is enough, so LOG = 18.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 18;                      // 2^18 > 2·10^5
int n, up[LOG][200001], dep[200001];
vector<int> ch[200001];

void build() {
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
    up[0][1] = 1;                        // above the founder: the founder
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];   // 2^k up = 2^(k-1) up, twice
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if (diff >> k & 1) u = up[k][u];    // lift u to v's depth
    if (u == v) return u;                // v was an ancestor of u
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

int main() {
    n = 200000;                          // a long line, plus one child of 3
    for (int v = 2; v <= n; v++) {
        up[0][v] = v < n ? v - 1 : 3;
        ch[up[0][v]].push_back(v);
    }
    build();
    ll sum = 0;
    for (int i = 0; i < 200000; i++)     // 2·10^5 deep queries
        sum += lca(n - 1 - i % 1000, n);
    cout << sum << "\n";
}
600000

Stress test against climbing

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 18;                      // 2^18 > 2·10^5
int n, up[LOG][200001], dep[200001];
vector<int> ch[200001];

void build() {
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
    up[0][1] = 1;                        // above the founder: the founder
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];   // 2^k up = 2^(k-1) up, twice
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if (diff >> k & 1) u = up[k][u];    // lift u to v's depth
    if (u == v) return u;                // v was an ancestor of u
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

int climb(int u, int v) {                // one generation at a time
    while (dep[u] > dep[v]) u = up[0][u];
    while (dep[v] > dep[u]) v = up[0][v];
    while (u != v) u = up[0][u], v = up[0][v];
    return u;
}

int main() {
    mt19937 rng(53);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 10 + 1;
        for (int v = 1; v <= n; v++) ch[v].clear();
        for (int v = 2; v <= n; v++) {       // random family tree
            up[0][v] = rng() % (v - 1) + 1;
            ch[up[0][v]].push_back(v);
        }
        build();
        for (int u = 1; u <= n; u++)
            for (int v = 1; v <= n; v++)     // every pair
                if (climb(u, v) != lca(u, v)) {
                    cout << "mismatch on test " << t;
                    return 0;
                }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

With only 10 people per test, even LOG = 17 passes this test, because no gap is ever that large. Small random tests catch logic bugs (like the missing u == v line); only a maximum-size test catches limits that are too small. Always run both.

Problem A2 · Courier Distance

(Written for this course.)

The villages and roads of episode 52: n villages, n − 1 roads, road i joins a_i and b_i with length w_i. Answer q questions: the road distance between u and v.

  • Input: n q (1 ≤ n, q ≤ 2 · 10^5), n − 1 lines a b w (1 ≤ w ≤ 10^9), then q lines u v.
  • Output: one distance per line (up to about 2 · 10^14, so long long).
6 4
1 2 3
2 3 4
2 4 2
4 5 6
1 6 1
5 3
6 5
3 4
2 2

The formula

Root the tree at village 1 and let dist[v] be the road length from village 1 to v (one BFS). The routes from 1 to u and from 1 to v share exactly the part from 1 down to their LCA, so

dist(u, v) = dist[u] + dist[v] − 2 · dist[lca(u, v)]

For (5, 3): dist[5] = 11, dist[3] = 7, lca = 2 with dist[2] = 3, so 11 + 7 − 6 = 12, the diameter from episode 52.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 18;
int n, up[LOG][200001], dep[200001];
ll dist[200001];                         // road length from village 1
vector<pair<int, int>> g[200001];        // (neighbour, length)

void build() {
    vector<int> bfs = {1};
    up[0][1] = 1;
    for (int i = 0; i < (int)bfs.size(); i++) {
        int v = bfs[i];
        for (auto [c, w] : g[v])
            if (c != up[0][v]) {             // not the way back up
                up[0][c] = v;
                dep[c] = dep[v] + 1;
                dist[c] = dist[v] + w;
                bfs.push_back(c);
            }
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if (diff >> k & 1) u = up[k][u];    // lift u to v's depth
    if (u == v) return u;                // v was an ancestor of u
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

ll route(int u, int v) {
    return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    build();
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << route(u, v) << "\n";
    }
}
12
12
6
0

The BFS walks two-way roads, so it skips the road back to the parent (c != up[0][v]). On a line of 2 · 10^5 villages with 10^9 per road and a question from the last village to every village:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 18;
int n, up[LOG][200001], dep[200001];
ll dist[200001];                         // road length from village 1
vector<pair<int, int>> g[200001];        // (neighbour, length)

void build() {
    vector<int> bfs = {1};
    up[0][1] = 1;
    for (int i = 0; i < (int)bfs.size(); i++) {
        int v = bfs[i];
        for (auto [c, w] : g[v])
            if (c != up[0][v]) {             // not the way back up
                up[0][c] = v;
                dep[c] = dep[v] + 1;
                dist[c] = dist[v] + w;
                bfs.push_back(c);
            }
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if (diff >> k & 1) u = up[k][u];    // lift u to v's depth
    if (u == v) return u;                // v was an ancestor of u
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

ll route(int u, int v) {
    return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}

int main() {
    n = 200000;                          // one long road, 10^9 per step
    for (int v = 1; v < n; v++) {
        g[v].push_back({v + 1, 1000000000});
        g[v + 1].push_back({v, 1000000000});
    }
    build();
    ll best = 0;
    for (int v = 1; v <= n; v++)         // 2·10^5 queries
        best = max(best, route(n, v));
    cout << best << "\n";
}
199999000000000

Problem A3 · Message Relay

(Written for this course.)

The family register again. A message travels from person u to person v along the family tree, passed hand to hand: up from u to the meeting point, then down to v. For each question u v k, print who holds the message after k handoffs (k = 0 means u). k is at most the number of steps on the route.

9 4
1 1 2 2 3 3 4 5
8 9 2
8 9 4
8 6 4
4 8 1

Up, then down

Let l = lca(u, v), a = dep[u] − dep[l] (steps up) and b = dep[v] − dep[l] (steps down). The route has a + b steps.

  • If k ≤ a, the message is still climbing: the answer is the k-th ancestor of u, kth(u, k).
  • Otherwise it is coming down. The table can only jump up, so count from v's end: the holder is a + b − k steps above v, kth(v, a + b − k).

kth(v, k) jumps by the bits of k, exactly like the lift inside lca (which is just kth(u, dep[u] − dep[v])).

The first try counted the way down as kth(v, k − a):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 18;                      // 2^18 > 2·10^5
int n, up[LOG][200001], dep[200001];
vector<int> ch[200001];

void build() {
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
    up[0][1] = 1;                        // above the founder: the founder
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];   // 2^k up = 2^(k-1) up, twice
}

int kth(int v, int k) {                 // k generations up
    for (int j = 0; j < LOG; j++)
        if (k >> j & 1) v = up[j][v];
    return v;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = kth(u, dep[u] - dep[v]);         // the lift is just kth
    if (u == v) return u;                // v was an ancestor of u
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

int stop(int u, int v, int k) {         // k-th person from u towards v
    int l = lca(u, v), a = dep[u] - dep[l], b = dep[v] - dep[l];
    if (k <= a) return kth(u, k);        // still climbing from u
    return kth(v, k - a);                // coming down to v
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int v = 2; v <= n; v++) {
        cin >> up[0][v];
        ch[up[0][v]].push_back(v);
    }
    build();
    while (q--) {
        int u, v, k;
        cin >> u >> v >> k;
        cout << stop(u, v, k) << "\n";
    }
}
2
2
3
4

k − a counts steps down from the meeting point, but kth climbs up from v: opposite directions. For (8, 9, 4) it gives 2 instead of 9.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 18;                      // 2^18 > 2·10^5
int n, up[LOG][200001], dep[200001];
vector<int> ch[200001];

void build() {
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
    up[0][1] = 1;                        // above the founder: the founder
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];   // 2^k up = 2^(k-1) up, twice
}

int kth(int v, int k) {                 // k generations up
    for (int j = 0; j < LOG; j++)
        if (k >> j & 1) v = up[j][v];
    return v;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = kth(u, dep[u] - dep[v]);         // the lift is just kth
    if (u == v) return u;                // v was an ancestor of u
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

int stop(int u, int v, int k) {         // k-th person from u towards v
    int l = lca(u, v), a = dep[u] - dep[l], b = dep[v] - dep[l];
    if (k <= a) return kth(u, k);        // still climbing from u
    return kth(v, a + b - k);            // coming down: count from v's end
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int v = 2; v <= n; v++) {
        cin >> up[0][v];
        ch[up[0][v]].push_back(v);
    }
    build();
    while (q--) {
        int u, v, k;
        cin >> u >> v >> k;
        cout << stop(u, v, k) << "\n";
    }
}
2
9
3
8

Stress test against writing the route out

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 18;                      // 2^18 > 2·10^5
int n, up[LOG][200001], dep[200001];
vector<int> ch[200001];

void build() {
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
    up[0][1] = 1;                        // above the founder: the founder
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];   // 2^k up = 2^(k-1) up, twice
}

int kth(int v, int k) {                 // k generations up
    for (int j = 0; j < LOG; j++)
        if (k >> j & 1) v = up[j][v];
    return v;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = kth(u, dep[u] - dep[v]);         // the lift is just kth
    if (u == v) return u;                // v was an ancestor of u
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

int stop(int u, int v, int k) {         // k-th person from u towards v
    int l = lca(u, v), a = dep[u] - dep[l], b = dep[v] - dep[l];
    if (k <= a) return kth(u, k);        // still climbing from u
    return kth(v, a + b - k);            // coming down: count from v's end
}

vector<int> walk(int u, int v) {         // brute: write the route out
    vector<int> L, R;
    while (dep[u] > dep[v]) L.push_back(u), u = up[0][u];
    while (dep[v] > dep[u]) R.push_back(v), v = up[0][v];
    while (u != v) L.push_back(u), R.push_back(v), u = up[0][u], v = up[0][v];
    L.push_back(u);
    L.insert(L.end(), R.rbegin(), R.rend());
    return L;
}

int main() {
    mt19937 rng(53);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 10 + 1;
        for (int v = 1; v <= n; v++) ch[v].clear();
        for (int v = 2; v <= n; v++) {
            up[0][v] = rng() % (v - 1) + 1;
            ch[up[0][v]].push_back(v);
        }
        build();
        for (int u = 1; u <= n; u++)
            for (int v = 1; v <= n; v++) {
                vector<int> p = walk(u, v);
                for (int k = 0; k < (int)p.size(); k++)
                    if (stop(u, v, k) != p[k]) {
                        cout << "mismatch on test " << t;
                        return 0;
                    }
            }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Build Per question Memory Verdict at n, q = 2 · 10^5
climb one generation at a time O(n) O(depth), up to O(n) O(n) TLE (4 · 10^10 steps)
binary lifting, LOG = 17 O(n log n) O(log n) 17 · n ints Wrong Answer on the max test
binary lifting, LOG = 18 O(n log n) ≈ 3.6 · 10^6 O(log n) ≤ 18 jumps 18 · 2 · 10^5 ints ≈ 14 MB accepted
distance with dist[] and the LCA O(n log n) O(log n) + n long long accepted
k-th person on a route O(n log n) O(log n) same table accepted
a BFS per distance question none O(n) O(n) TLE

Common mistakes (and the real outputs)

Mistake What you see Why Fix
climbing one step at a time Time Limit Exceeded O(n) per question binary lifting
no if (u == v) return u; after the lift 2 1 2 3 (expected 2 1 4 7) v was an ancestor of u return u when they meet
LOG = 17 for n = 2 · 10^5 800000 (expected 600000) 2^17 − 1 < the depth gap 2^LOG > n − 1, LOG = 18
jumping while up[k][u] == up[k][v] answers too high (often the root) equal can be above the meeting point jump only while different
kth(v, k - a) on the way down 2 2 3 4 (expected 2 9 3 8) kth climbs up from v kth(v, a + b - k)
distances in int wrapped answers up to 2 · 10^14 long long dist[]
recursive DFS for depths on a long line Runtime Error (stack overflow) 2 · 10^5 nested calls BFS or your own stack
filling row k before row k − 1 is complete wrong table row k reads row k − 1 for every v loop k outside, v inside

Mini project

Write an LCA toolbox for a rooted tree: build(), kth(v, k), lca(u, v), dist(u, v), onPath(u, v, x) (is x on the route?) and stop(u, v, k). Test it on four shapes (a line, a star, a "broom" like the maximum test above and a random tree) for n = 10, 1000 and 2 · 10^5. Check the small ones against climbing, and time the big ones: doubling n should only add a little time per question. As a bonus, add a second table of maximum road lengths (homework 1) and print the heaviest road on every route.

Practice

These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).

1. The heaviest road on the route. Same input as Courier Distance. For each question print the largest road length on the route from u to v (0 if u = v).

Solution

Next to each jump store the maximum road it passes: mx[0][c] is the road from c to its parent and mx[k][v] = max(mx[k−1][v], mx[k−1][up[k−1][v]]). Every jump in the lift and in the jump phase adds its mx to the answer, and at the end the two roads into the LCA are added.

#include <bits/stdc++.h>
using namespace std;

const int LOG = 18;
int n, up[LOG][200001], mx[LOG][200001], dep[200001];
vector<pair<int, int>> g[200001];          // (neighbour, weight)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    vector<int> bfs = {1};
    up[0][1] = 1;                          // mx[0][1] = 0: no road above the root
    for (int i = 0; i < (int)bfs.size(); i++) {
        int v = bfs[i];
        for (auto [c, w] : g[v])
            if (c != up[0][v]) {
                up[0][c] = v, mx[0][c] = w, dep[c] = dep[v] + 1;
                bfs.push_back(c);
            }
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++) {
            up[k][v] = up[k - 1][up[k - 1][v]];
            mx[k][v] = max(mx[k - 1][v], mx[k - 1][up[k - 1][v]]);   // max over the 2^k roads above v
        }
    while (q--) {
        int u, v, best = 0;
        cin >> u >> v;
        if (dep[u] < dep[v]) swap(u, v);
        int diff = dep[u] - dep[v];
        for (int k = 0; k < LOG; k++)
            if (diff >> k & 1) best = max(best, mx[k][u]), u = up[k][u];
        if (u != v) {
            for (int k = LOG - 1; k >= 0; k--)
                if (up[k][u] != up[k][v]) {
                    best = max({best, mx[k][u], mx[k][v]});
                    u = up[k][u], v = up[k][v];
                }
            best = max({best, mx[0][u], mx[0][v]});   // the last two roads into the LCA
        }
        cout << best << "\n";
    }
}
6
6
4
0

2. Is u an ancestor of v? Family register input; each question u v prints YES or NO.

Solution

u is an ancestor of v exactly when u is not deeper and jumping dep[v] − dep[u] up from v lands on u: O(log n). Episode 54 answers it in O(1) with entry times.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 18;
int n, up[LOG][200001], dep[200001];
vector<int> ch[200001];

void build() {
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
    up[0][1] = 1;
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];
}

int kth(int v, int k) {
    for (int j = 0; j < LOG; j++)
        if (k >> j & 1) v = up[j][v];
    return v;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = kth(u, dep[u] - dep[v]);
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

bool above(int u, int v) {                 // is u an ancestor of v?
    return dep[u] <= dep[v] && kth(v, dep[v] - dep[u]) == u;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int v = 2; v <= n; v++) {
        cin >> up[0][v];
        ch[up[0][v]].push_back(v);
    }
    build();
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << (above(u, v) ? "YES" : "NO") << "\n";
    }
}
YES
NO
YES
NO
YES

3. People exactly k steps from u. Family register input; each question u k prints how many people are exactly k steps (along family links, up or down) from u.

Solution

For one question, a BFS from u over the links in both directions that stops at depth k is O(n). Reset only the distances you touched, so a question costs only what it visits. For many questions on a big tree this needs centroid decomposition (episode 56).

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> g[200001];                     // family links in both directions

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int v = 2; v <= n; v++) {
        int p;
        cin >> p;
        g[p].push_back(v);
        g[v].push_back(p);
    }
    vector<int> d(n + 1, -1);
    while (q--) {
        int u, k, cnt = 0;
        cin >> u >> k;
        vector<int> bfs = {u}, seen = {u};
        d[u] = 0;
        for (int i = 0; i < (int)bfs.size(); i++) {
            int v = bfs[i];
            if (d[v] == k) { cnt++; continue; }   // no need to go further
            for (int x : g[v])
                if (d[x] < 0) d[x] = d[v] + 1, bfs.push_back(x), seen.push_back(x);
        }
        for (int v : seen) d[v] = -1;          // reset only what we touched
        cout << cnt << "\n";
    }
}
1
2
2
1

4. The LCA when the root changes. Family register input, but each question r u v asks for the LCA of u and v if the tree were rooted at r.

Solution

A classic fact: with the tree rooted at 1, the answer is the deepest of lca(u, v), lca(u, r) and lca(v, r). It is the vertex of the u–v route closest to r.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 18;
int n, up[LOG][200001], dep[200001];
vector<int> ch[200001];

void build() {
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
    up[0][1] = 1;
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];
}

int kth(int v, int k) {
    for (int j = 0; j < LOG; j++)
        if (k >> j & 1) v = up[j][v];
    return v;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = kth(u, dep[u] - dep[v]);
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int v = 2; v <= n; v++) {
        cin >> up[0][v];
        ch[up[0][v]].push_back(v);
    }
    build();
    while (q--) {
        int r, u, v;
        cin >> r >> u >> v;
        int a = lca(u, v), b = lca(u, r), c = lca(v, r);
        int ans = a;                           // the deepest of the three
        if (dep[b] > dep[ans]) ans = b;
        if (dep[c] > dep[ans]) ans = c;
        cout << ans << "\n";
    }
}
2
2
2
3

Quick quiz

A million people stand in one long line of generations (n = 10^6). What is the smallest LOG that works?

const int LOG = ?;   // up[LOG][1000001]

A) 17 · B) 19 · C) 20 · D) 21

Answer

C. The deepest gap is 999 999. 2^19 = 524 288 is too small; 2^20 = 1 048 576 is enough, so the jumps 2^0 … 2^19 (LOG = 20 rows) can make any climb.

Interview questions

  1. What is the LCA, and how do you compute it for many queries? The deepest common ancestor of two vertices in a rooted tree. Binary lifting: O(n log n) preprocessing, O(log n) per query. Alternatives: Euler tour + sparse table (O(1) per query), or Tarjan's offline algorithm.
  2. Why does binary lifting work? Any climb d is a sum of distinct powers of two (its binary digits), and up[k] is built from up[k − 1] by applying it twice.
  3. Why do we jump only while up[k][u] != up[k][v]? An equal result may be the LCA or something above it; differing results are certainly below the LCA, so it is safe to jump. This ends one step below the LCA.
  4. How big must LOG be? 2^LOG must exceed the maximum depth, i.e. LOG ≥ ⌈log₂ n⌉ (18 for 2 · 10^5, 20 for 10^6).
  5. How do you get the distance between two nodes? dist[u] + dist[v] − 2 · dist[lca(u, v)] with dist from the root.
  6. How do you find the k-th node on the path from u to v? With l = lca, a = dep[u] − dep[l], b = dep[v] − dep[l]: kth(u, k) if k ≤ a, else kth(v, a + b − k).
  7. What is the memory cost? LOG · n integers: 18 · 2 · 10^5 ≈ 3.6 · 10^6 ints ≈ 14 MB.

Glossary

Term Meaning Example
Rooted tree A tree with one vertex chosen as the top the family, rooted at the founder
Root The top vertex of a rooted tree person 1, the founder
Parent / child The neighbour one step towards the root / away from it 4 is the parent of 8
Ancestor The vertex itself, its parent, its parent's parent, … up to the root 1, 2, 4, 8 are ancestors of 8
Descendant v is a descendant of u when u is an ancestor of v 8 is a descendant of 2
Depth Number of steps from the root depth(8) = 3
Common ancestor A vertex that is an ancestor of both u and v 1 and 2 for (8, 9)
LCA (lowest common ancestor) The deepest common ancestor lca(8, 9) = 2
Climbing Moving to the parent one step at a time climb(u, v)
BFS (breadth-first search) Visiting vertices level by level from a start; parents before children depths()
Jump table up[k][v] = the vertex 2^k steps above v up[1][8] = 2
Binary lifting Jumping by powers of two to climb any distance in O(log n) 13 = 8 + 4 + 1
LOG The number of rows of the jump table; 2^LOG must exceed the depth 18 for 2 · 10^5
Binary representation Writing a number as a sum of powers of two 13 = 1101₂
Bit test d >> k & 1 1 when bit k of d is set 13 >> 2 & 1 = 1
Lift Jumping the deeper vertex up by the depth gap phase 1 of lca
k-th ancestor The vertex k steps above v kth(14, 13) = 1
dist[v] The road length from the root to v dist[5] = 11
Route (path) The unique sequence of vertices between two vertices of a tree 8, 4, 2, 5, 9
Edge case A small or extreme input that breaks careless code n = 1; u = v; u an ancestor of v
Maximum test An input at the largest allowed size the 2 · 10^5 broom
Stress test Comparing a fast solution with a slow, surely-correct one on many random inputs all 500 tests passed
mt19937 C++'s Mersenne Twister random number generator mt19937 rng(53);
O(log n) Time growing with the number of binary digits of n ≤ 18 jumps
O(n log n) n times log n, the cost of building the table 3.6 · 10^6 entries
Time Limit Exceeded (TLE) The program is too slow for the time limit climbing
Wrong Answer (WA) The program prints a wrong output 2 1 2 3, 800000
long long 64-bit integer, up to about 9.2 · 10^18 distances up to 2 · 10^14
Euler tour Writing vertices in DFS visiting order so subtrees become ranges next episode

Summary

  • The LCA is where the two lines from u and v up to the root first meet; a vertex counts as its own ancestor.
  • Climbing one step at a time is O(depth) per question: TLE on a long line.
  • Jump table: up[k][v] = up[k−1][up[k−1][v]], LOG rows, built in O(n log n); set up[0][root] = root.
  • lca(u, v): lift the deeper one by the bits of the gap; if equal, return; jump both from the biggest k down while different; answer the parent.
  • 2^LOG must exceed the depth: LOG = 17 prints 800000 instead of 600000 at n = 2 · 10^5; LOG = 18 is right. Small stress tests cannot catch this, the maximum test can.
  • dist(u, v) = dist[u] + dist[v] − 2 · dist[lca], in long long.
  • k-th on a route: kth(u, k) while climbing, kth(v, a + b − k) on the way down.

Solutions in C++, Java and Python

Problem A1 · Family Register

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 18;                      // 2^18 > 2·10^5
int n, up[LOG][200001], dep[200001];
vector<int> ch[200001];

void build() {
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
    up[0][1] = 1;                        // above the founder: the founder
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];   // 2^k up = 2^(k-1) up, twice
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if (diff >> k & 1) u = up[k][u];    // lift u to v's depth
    if (u == v) return u;                // v was an ancestor of u
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int v = 2; v <= n; v++) {
        cin >> up[0][v];
        ch[up[0][v]].push_back(v);
    }
    build();
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static final int LOG = 18;
    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = nextInt(in), q = nextInt(in);
        int[][] up = new int[LOG][n + 1];
        int[] dep = new int[n + 1], head = new int[n + 1], next = new int[n + 1];
        Arrays.fill(head, 0);
        for (int v = 2; v <= n; v++) {               // children as linked lists
            up[0][v] = nextInt(in);
            next[v] = head[up[0][v]];
            head[up[0][v]] = v;
        }
        int[] bfs = new int[n];
        int len = 0;
        bfs[len++] = 1;
        for (int i = 0; i < len; i++)
            for (int c = head[bfs[i]]; c != 0; c = next[c]) {
                dep[c] = dep[bfs[i]] + 1;
                bfs[len++] = c;
            }
        up[0][1] = 1;
        for (int k = 1; k < LOG; k++)
            for (int v = 1; v <= n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            int u = nextInt(in), v = nextInt(in);
            if (dep[u] < dep[v]) { int t = u; u = v; v = t; }
            int diff = dep[u] - dep[v];
            for (int k = 0; k < LOG; k++) if ((diff >> k & 1) == 1) u = up[k][u];
            if (u != v) {
                for (int k = LOG - 1; k >= 0; k--)
                    if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
                u = up[0][u];
            }
            sb.append(u).append('\n');
        }
        System.out.print(sb);
    }
    static int nextInt(DataInputStream in) throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
        return r;
    }
}
2
1
4
7

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    LOG = max(1, n.bit_length())
    par = [0, 1] + [int(x) for x in data[2:n + 1]]   # par[1] = 1: above the founder
    ch = [[] for _ in range(n + 1)]
    for v in range(2, n + 1):
        ch[par[v]].append(v)
    dep = [0] * (n + 1)
    bfs = [1]
    for v in bfs:                                   # the list grows while we walk it
        for c in ch[v]:
            dep[c] = dep[v] + 1
            bfs.append(c)
    up = [par]
    for k in range(1, LOG):
        prev = up[-1]
        up.append([prev[prev[v]] for v in range(n + 1)])
    out = []
    pos = n + 1
    for _ in range(q):
        u, v = int(data[pos]), int(data[pos + 1])
        pos += 2
        if dep[u] < dep[v]:
            u, v = v, u
        diff = dep[u] - dep[v]
        k = 0
        while diff:
            if diff & 1:
                u = up[k][u]
            diff >>= 1
            k += 1
        if u != v:
            for k in range(LOG - 1, -1, -1):
                if up[k][u] != up[k][v]:
                    u, v = up[k][u], up[k][v]
            u = up[0][u]
        out.append(u)
    print("\n".join(map(str, out)))

main()
2
1
4
7

Problem A2 · Courier Distance

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 18;
int n, up[LOG][200001], dep[200001];
ll dist[200001];                         // road length from village 1
vector<pair<int, int>> g[200001];        // (neighbour, length)

void build() {
    vector<int> bfs = {1};
    up[0][1] = 1;
    for (int i = 0; i < (int)bfs.size(); i++) {
        int v = bfs[i];
        for (auto [c, w] : g[v])
            if (c != up[0][v]) {             // not the way back up
                up[0][c] = v;
                dep[c] = dep[v] + 1;
                dist[c] = dist[v] + w;
                bfs.push_back(c);
            }
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if (diff >> k & 1) u = up[k][u];    // lift u to v's depth
    if (u == v) return u;                // v was an ancestor of u
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

ll route(int u, int v) {
    return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    build();
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << route(u, v) << "\n";
    }
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static final int LOG = 18;
    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = nextInt(in), q = nextInt(in);
        int[] head = new int[n + 1], nxt = new int[2 * n], to = new int[2 * n], w = new int[2 * n];
        Arrays.fill(head, -1);
        for (int i = 0, e = 0; i < n - 1; i++) {
            int a = nextInt(in), b = nextInt(in), c = nextInt(in);
            to[e] = b; w[e] = c; nxt[e] = head[a]; head[a] = e++;
            to[e] = a; w[e] = c; nxt[e] = head[b]; head[b] = e++;
        }
        int[][] up = new int[LOG][n + 1];
        int[] dep = new int[n + 1], bfs = new int[n];
        long[] dist = new long[n + 1];
        int len = 0;
        bfs[len++] = 1;
        up[0][1] = 1;
        for (int i = 0; i < len; i++) {
            int v = bfs[i];
            for (int e = head[v]; e != -1; e = nxt[e]) {
                int c = to[e];
                if (c == up[0][v]) continue;           // the way back up
                up[0][c] = v; dep[c] = dep[v] + 1; dist[c] = dist[v] + w[e];
                bfs[len++] = c;
            }
        }
        for (int k = 1; k < LOG; k++)
            for (int v = 1; v <= n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            int u = nextInt(in), v = nextInt(in), a = u, b = v;
            if (dep[a] < dep[b]) { int t = a; a = b; b = t; }
            int diff = dep[a] - dep[b];
            for (int k = 0; k < LOG; k++) if ((diff >> k & 1) == 1) a = up[k][a];
            if (a != b) {
                for (int k = LOG - 1; k >= 0; k--)
                    if (up[k][a] != up[k][b]) { a = up[k][a]; b = up[k][b]; }
                a = up[0][a];
            }
            sb.append(dist[u] + dist[v] - 2 * dist[a]).append('\n');
        }
        System.out.print(sb);
    }
    static int nextInt(DataInputStream in) throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
        return r;
    }
}
12
12
6
0

Python (Python integers never overflow, so no long long worries)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    LOG = max(1, n.bit_length())
    g = [[] for _ in range(n + 1)]
    pos = 2
    for _ in range(n - 1):
        a, b, w = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])
        pos += 3
        g[a].append((b, w))
        g[b].append((a, w))
    par = [0] * (n + 1)
    par[1] = 1
    dep = [0] * (n + 1)
    dist = [0] * (n + 1)                            # Python ints never overflow
    bfs = [1]
    for v in bfs:
        for c, w in g[v]:
            if c != par[v]:
                par[c], dep[c], dist[c] = v, dep[v] + 1, dist[v] + w
                bfs.append(c)
    up = [par]
    for k in range(1, LOG):
        prev = up[-1]
        up.append([prev[prev[v]] for v in range(n + 1)])

    def lca(u, v):
        if dep[u] < dep[v]:
            u, v = v, u
        diff, k = dep[u] - dep[v], 0
        while diff:
            if diff & 1:
                u = up[k][u]
            diff >>= 1
            k += 1
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                u, v = up[k][u], up[k][v]
        return up[0][u]

    out = []
    for _ in range(q):
        u, v = int(data[pos]), int(data[pos + 1])
        pos += 2
        out.append(dist[u] + dist[v] - 2 * dist[lca(u, v)])
    print("\n".join(map(str, out)))

main()
12
12
6
0

Problem A3 · Message Relay

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LOG = 18;                      // 2^18 > 2·10^5
int n, up[LOG][200001], dep[200001];
vector<int> ch[200001];

void build() {
    vector<int> bfs = {1};
    for (int i = 0; i < (int)bfs.size(); i++)
        for (int c : ch[bfs[i]]) {
            dep[c] = dep[bfs[i]] + 1;
            bfs.push_back(c);
        }
    up[0][1] = 1;                        // above the founder: the founder
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];   // 2^k up = 2^(k-1) up, twice
}

int kth(int v, int k) {                 // k generations up
    for (int j = 0; j < LOG; j++)
        if (k >> j & 1) v = up[j][v];
    return v;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = kth(u, dep[u] - dep[v]);         // the lift is just kth
    if (u == v) return u;                // v was an ancestor of u
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
    return up[0][u];
}

int stop(int u, int v, int k) {         // k-th person from u towards v
    int l = lca(u, v), a = dep[u] - dep[l], b = dep[v] - dep[l];
    if (k <= a) return kth(u, k);        // still climbing from u
    return kth(v, a + b - k);            // coming down: count from v's end
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int v = 2; v <= n; v++) {
        cin >> up[0][v];
        ch[up[0][v]].push_back(v);
    }
    build();
    while (q--) {
        int u, v, k;
        cin >> u >> v >> k;
        cout << stop(u, v, k) << "\n";
    }
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static final int LOG = 18;
    static int[][] up;
    static int[] dep;

    static int kth(int v, int k) {
        for (int j = 0; j < LOG; j++) if ((k >> j & 1) == 1) v = up[j][v];
        return v;
    }
    static int lca(int u, int v) {
        if (dep[u] < dep[v]) { int t = u; u = v; v = t; }
        u = kth(u, dep[u] - dep[v]);
        if (u == v) return u;
        for (int k = LOG - 1; k >= 0; k--)
            if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
        return up[0][u];
    }
    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = nextInt(in), q = nextInt(in);
        up = new int[LOG][n + 1];
        dep = new int[n + 1];
        int[] head = new int[n + 1], next = new int[n + 1];
        for (int v = 2; v <= n; v++) {
            up[0][v] = nextInt(in);
            next[v] = head[up[0][v]];
            head[up[0][v]] = v;
        }
        int[] bfs = new int[n];
        int len = 0;
        bfs[len++] = 1;
        for (int i = 0; i < len; i++)
            for (int c = head[bfs[i]]; c != 0; c = next[c]) { dep[c] = dep[bfs[i]] + 1; bfs[len++] = c; }
        up[0][1] = 1;
        for (int k = 1; k < LOG; k++)
            for (int v = 1; v <= n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            int u = nextInt(in), v = nextInt(in), k = nextInt(in);
            int l = lca(u, v), a = dep[u] - dep[l], b = dep[v] - dep[l];
            sb.append(k <= a ? kth(u, k) : kth(v, a + b - k)).append('\n');
        }
        System.out.print(sb);
    }
    static int nextInt(DataInputStream in) throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
        return r;
    }
}
2
9
3
8

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    LOG = max(1, n.bit_length())
    par = [0, 1] + [int(x) for x in data[2:n + 1]]
    ch = [[] for _ in range(n + 1)]
    for v in range(2, n + 1):
        ch[par[v]].append(v)
    dep = [0] * (n + 1)
    bfs = [1]
    for v in bfs:
        for c in ch[v]:
            dep[c] = dep[v] + 1
            bfs.append(c)
    up = [par]
    for k in range(1, LOG):
        prev = up[-1]
        up.append([prev[prev[v]] for v in range(n + 1)])

    def kth(v, k):
        j = 0
        while k:
            if k & 1:
                v = up[j][v]
            k >>= 1
            j += 1
        return v

    def lca(u, v):
        if dep[u] < dep[v]:
            u, v = v, u
        u = kth(u, dep[u] - dep[v])
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                u, v = up[k][u], up[k][v]
        return up[0][u]

    out = []
    pos = n + 1
    for _ in range(q):
        u, v, k = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])
        pos += 3
        l = lca(u, v)
        a, b = dep[u] - dep[l], dep[v] - dep[l]
        out.append(kth(u, k) if k <= a else kth(v, a + b - k))
    print("\n".join(map(str, out)))

main()
2
9
3
8

In Python, 2 · 10^5 questions with up to 18 jumps each can be slow under CPython; submit with PyPy if the judge offers it.