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)
- 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.
- Check. If u == v now, v was an ancestor of u: return it.
- 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. - 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
- 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.
- 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.
- 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. - 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).
- How do you get the distance between two nodes? dist[u] + dist[v] − 2 · dist[lca(u, v)] with dist from the root.
- 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).
- 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); setup[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
800000instead of600000at 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.