⚙️AlgorithmIntermediate

LCA - Binary Lifting

Key Points

•
Binary lifting precomputes 2^k ancestors for every node so we can jump upward in powers of two.
•
Build the up table in O(n $lo g$ n) time using the recurrence up[v][k] = up[ up[v][k-1] ][k-1].
•
To find LCA(u, v), first lift the deeper node to the same depth, then lift both together until they meet.
•
Queries such as k-th ancestor, distance, and k-th node on a path are all O( $lo g$ n) with binary lifting.
•
You can store extra information (sum, max, min) alongside each 2^k jump to answer path queries in O( $lo g$ n).
•
Memory usage is O(n $lo g$ n) for the jump table (and the same factor per extra attribute you store).
•
Handle roots, depths, and 'null' ancestors carefully to avoid off-by-one and out-of-bounds errors.
•
Binary lifting is ideal for static trees with many queries; for dynamic trees, consider other data structures.

Prerequisites

→Trees and rooted trees — Understanding parent-child relations, depth, and unique simple paths is essential for LCA.
→BFS/DFS graph traversal — You must compute parents and depths before building jump tables.
→Binary representation and bit operations — Binary lifting relies on decomposing jumps into powers of two via set bits.
→Asymptotic analysis — To evaluate the O(n log n) preprocessing and O(log n) query guarantees.
→Associative operations — Path aggregates require combining segments with an associative function and an identity.

Detailed Explanation

Tap terms for definitions

01Overview

Lowest Common Ancestor (LCA) is a fundamental tree problem: given two nodes u and v in a rooted tree, their LCA is the deepest node that is an ancestor of both. Binary lifting is a powerful technique to answer LCA queries and many related queries quickly after a one-time preprocessing step. The core idea is to precompute, for each node v and each k, the 2^k-th ancestor of v. With this table, any upward movement by K steps can be decomposed into jumps of powers of two according to the binary representation of K. This enables answering queries such as LCA, k-th ancestor, distance between nodes, and even path aggregates like sum or max if we store extra data with each jump.

The preprocessing builds a table up[v][k] where up[v][0] is v’s parent, up[v][1] is the grandparent, and so on. The recurrence up[v][k] = up[ up[v][k-1] ][k-1] allows filling the table in layers. Once built, LCA queries run in O(log n): lift the deeper node up to the shallower one’s depth, then lift both in decreasing powers of two to just before their LCA, and finally step to the parent. Binary lifting is widely used in competitive programming because it is simple, fast, and versatile for static trees.

02Intuition & Analogies

Imagine a very tall building where each floor is a node, and 'parent' means the floor immediately above. If you want to move up 137 floors, taking one step at a time would be too slow. Instead, suppose the building has teleporters that jump you up by 1, 2, 4, 8, 16, ... floors. With these, you can decompose 137 into 128 + 8 + 1 and reach your target in just three teleports. This is the essence of binary lifting: prebuild power-of-two 'teleporters' for each node so any upward travel can be broken into a few large jumps.

For LCA, picture two people on different floors wanting to find the highest floor they both can reach by only going upward (toward the root). First, if one person is lower, give them teleporters to quickly match the other’s height (depth). Now both are on the same level. Next, you want to move them upward together, using the largest possible teleporters that keep them on different paths (i.e., their ancestors differ). When no bigger teleporter keeps them apart, the next step is the same for both—they converge at their lowest common meeting point, which is the LCA.

If each teleporter also tells you something about the segment it jumps over—like the total toll (sum), the roughest segment (max), or the smallest segment (min)—you can accumulate these values while jumping. Because any path can be split into O(log n) teleporter jumps, the total work remains logarithmic while answering richer path queries. The big picture: prepare big, reusable jumps and attach the information you’ll need. Then, almost any upward path query becomes a quick sequence of binary decisions.

03Formal Definition

Let T be a rooted tree with n nodes labeled 1..n, parent function parent(v) (with parent(root) = 0), and depth function depth(v) giving the distance in edges from the root. Define a jump table up[v][k] for integers v in [1..n] and k in [0..

⌊ lo g_{2}

⌋

] by: - up[v][0] = parent(v), and - for

k > 0

, up[v][k] = up[ up[v][k-1] ][k-1], with the convention up[0][k] = 0. This definition ensures up[v][k] is the 2^k-th ancestor of v (or 0 if it does not exist). For any nonnegative integer K with binary expansion K =

\sum_{i = 0}^{b}

b_{i}

2^i where

b_{i}

\in

{0,1}, the K-th ancestor of v is obtained by successively applying up[v][i] for each i with

b_{i} = 1

. The Lowest Common Ancestor of two nodes u and v is the unique node w of maximum depth such that w is an ancestor of both u and v. An O(

lo g

n) LCA(u, v) algorithm proceeds as follows: (1) If depth(u) < depth(v), swap; (2) Lift u by depth(u) - depth(v) using the binary decomposition; (3) If

u = v

, return u; (4) For i from

⌊ lo g_{2}

⌋

down to 0, if up[u][i]

\neq =

up[v][i], set

u = u p [u] [i]

v = u p [v] [i];

(5) Return parent(u) (which equals parent(v)). For path queries, let A[v][k] be an aggregate (e.g., sum or max) over the path segment from v up to up[v][k]. Then we maintain A[v][k] satisfying A[v][k] = combine(A[v][k-1], A[ up[v][k-1] ][k-1]) with an associative combine operator and appropriate identity element.

04When to Use

Use binary lifting when you have a static tree (or forest) with many queries involving ancestors, LCAs, distances, or aggregates along root-to-node or node-to-node paths. It shines in settings like competitive programming where preprocessing time O(n \log n) and memory O(n \log n) are acceptable, and each query must be answered in O(\log n) or better.

Typical applications include: (1) LCA for path length queries: distance(u, v) = depth(u) + depth(v) - 2·depth(LCA(u, v)); (2) K-th ancestor queries: find the ancestor k steps above a node; (3) K-th node on a path between u and v, useful in tree navigation problems; (4) Path aggregates like sum, min, or max of edge weights or node values by storing extra data for each 2^k jump; (5) Functional graphs (each node has exactly one outgoing edge) for k-step jumps, though not a tree, the same jump table idea applies.

Avoid binary lifting when: (a) the tree changes frequently (edge insertions/deletions or re-rooting with updates), where Link-Cut Trees, Euler Tour + RMQ with rebuilds, or Heavy-Light Decomposition may be better; (b) memory is very tight and n is large—since O(n \log n) can be heavy; (c) you need arbitrary segment queries on paths that are not easily expressed with upward-only jumps—then Heavy-Light Decomposition with a segment tree often fits better.

⚠️Common Mistakes

Wrong LOG size: If LOG is too small, you may access out of bounds or miss ancestors near the root. Compute LOG as the smallest integer with 2^LOG > n. 2) Not initializing up[0][k] = 0: Always set the dummy ancestor of 0 to 0 so chained lookups like up[ up[v][k-1] ][k-1] are safe when an ancestor doesn’t exist.
Depth mismatches: Forgetting to compute depths consistently (e.g., root depth = 0) leads to incorrect lifting. Ensure you run a BFS/DFS from the root(s) to set depth and parent before building higher powers. 4) Recursion limits: A deep recursive DFS can stack overflow on large trees. Prefer iterative DFS/BFS or raise recursion limits cautiously.
Off-by-one in lifting: Mixing 0-indexed and 1-indexed steps in kthAncestor. Decide whether k = 0 returns the node itself (common) and document it. 6) Path aggregates double counting: When combining u→L and v→L segments for edge-based aggregates, do not add anything at L twice. For node-based aggregates, handle the L node according to your convention (include once).
Forests and unreachable pairs: LCA is undefined for nodes in different components. Track component IDs; if comp[u] ≠ comp[v], return a sentinel. 8) Re-rooting on the fly: Binary lifting tables are tied to the chosen root. If the root changes often, either rebuild or use an algorithm that supports dynamic roots explicitly. 9) Overflow: Use 64-bit types (long long) for sums or large weights. 10) Memory blow-up with many attributes: Each extra stored attribute multiplies memory by O(\log n); store only what you need.

Key Formulas

Jump Table Recurrence

u p [v] [0] = p a re n t (v), u p [v] [k] = u p [u p [v] [k - 1]] [k - 1]

Explanation: The 2^k-th ancestor of v is obtained by jumping 2^{k-1} twice. This fills the table in O(n $lo g$ n).

Binary Decomposition

K = i = 0 \sum b b_{i} 2^{i}, b_{i} \in {0, 1}

Explanation: Any integer K can be written as a sum of powers of two. To lift K steps, apply jumps for each set bit.

K-th Ancestor via Bits

kthAncestor (v, K) = u p^{(K)} (v) by applying set bits of K

Explanation: Use the binary representation of K to jump using up[v][i] whenever bit i is set, updating v each time.

LCA Notation

L = LCA (u, v)

Explanation: L denotes the lowest common ancestor of u and v, the deepest shared ancestor node.

Distance in a Tree

dist (u, v) = d e pt h (u) + d e pt h (v) - 2 d e pt h (L)

Explanation: The path from u to v goes up from u to LCA and then down from LCA to v. The formula counts its edges.

Time and Space Complexity

T_{b u i l d} (n) = O (n lo g n), T_{q u ery} (1) = O (lo g n), M (n) = O (n lo g n)

Explanation: Preprocessing time and memory grow linearly with n times the number of levels ( $lo g$ n). Each query touches at most LOG levels.

Depth Alignment

d = d e pt h (u) - d e pt h (v), u \leftarrow lift (u, d)

Explanation: First level the depths by lifting the deeper node up by the difference d using binary decomposition.

Simultaneous Lifting

For i = ⌊ lo g_{2} n ⌋ ..0 : if u p [u] [i] \neq = u p [v] [i], u \leftarrow u p [u] [i], v \leftarrow u p [v] [i]

Explanation: Lift both nodes by the largest possible equal jumps that keep their ancestors different, stopping just below the LCA.

Table Size

M = n \cdot (⌊ lo g_{2} n ⌋ + 1)

Explanation: The up table has one row per node and one column per power of two up to LOG.

Aggregate Recurrence

A [v] [k] = combine (A [v] [k - 1], A [u p [v] [k - 1]] [k - 1])

Explanation: Aggregates for 2^k jumps are formed by combining the two 2^{k-1} segments if the operation is associative.

Complexity Analysis

Let n be the number of nodes and LOG = ⌊log2 n⌋ + 1. Building the ancestor table up[v][k] requires computing parents and depths (O(n)) and then filling LOG−1 additional levels. For each level k and each node v, we compute up[v][k] via a constant-time lookup, totaling O(n · LOG) time. Memory usage is O(n · LOG) integers for the jump table. If we store extra attributes (e.g., sums and maxima), each attribute introduces another O(n · LOG) array, multiplying memory by the number of attributes. Each query touches at most LOG table entries. For LCA(u, v), we lift the deeper node by the depth difference using O(LOG) bit checks, then lift both nodes together for another O(LOG) steps, so T_

q u ery = O (L OG

). K-th ancestor queries are O(LOG) by scanning K’s bits. Distance queries and k-th node on a path both rely on one LCA call plus a constant number of lifts, remaining O(LOG). With weighted path aggregates, we maintain A[v][k] alongside up[v][k]; both lifting phases accumulate aggregates in O(LOG). Thus, path sum/max queries still take O(LOG). Overall, the trade-off is a one-time O(n log n) preprocessing and O(n log n) memory in exchange for fast O(log n) per query. For very large n where memory is constrained, consider lighter alternatives (e.g., Euler tour + RMQ uses O(n) memory but answers LCA in O(1) with more complex setup).

Code Examples

Basic LCA with Binary Lifting (k-th ancestor and distance)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct LCA {
5     int n, LOG;
6     int root;
7     vector<vector<int>> up;    // up[v][k] = 2^k-th ancestor of v
8     vector<int> depth;         // depth from root
9     vector<vector<int>> adj;   // adjacency list (1-indexed)
10 
11     LCA(int n_, int root_=1): n(n_), root(root_) {
12         LOG = 1;
13         while ((1 << LOG) <= n) ++LOG; // smallest LOG with 2^LOG > n
14         up.assign(n + 1, vector<int>(LOG, 0));
15         depth.assign(n + 1, 0);
16         adj.assign(n + 1, {});
17     }
18 
19     void add_edge(int u, int v) {
20         adj[u].push_back(v);
21         adj[v].push_back(u);
22     }
23 
24     void build() {
25         // BFS from root to set depth and first ancestors
26         queue<int> q;
27         vector<int> vis(n + 1, 0);
28         vis[root] = 1;
29         depth[root] = 0;
30         up[root][0] = 0; // parent of root is 0 (null)
31         q.push(root);
32         while (!q.empty()) {
33             int v = q.front(); q.pop();
34             for (int to : adj[v]) if (!vis[to]) {
35                 vis[to] = 1;
36                 depth[to] = depth[v] + 1;
37                 up[to][0] = v; // parent
38                 q.push(to);
39             }
40         }
41         // Build higher powers using DP
42         for (int k = 1; k < LOG; ++k) {
43             for (int v = 1; v <= n; ++v) {
44                 int mid = up[v][k-1];
45                 up[v][k] = (mid == 0 ? 0 : up[mid][k-1]);
46             }
47         }
48     }
49 
50     int kth_ancestor(int v, int k) const {
51         // Returns the node k steps above v (k=0 returns v). Returns 0 if it does not exist.
52         for (int i = 0; i < LOG && v != 0; ++i) {
53             if (k & (1 << i)) v = up[v][i];
54         }
55         return v;
56     }
57 
58     int lca(int a, int b) const {
59         if (depth[a] < depth[b]) swap(a, b);
60         int d = depth[a] - depth[b];
61         a = kth_ancestor(a, d);
62         if (a == b) return a;
63         for (int k = LOG - 1; k >= 0; --k) {
64             if (up[a][k] != up[b][k]) {
65                 a = up[a][k];
66                 b = up[b][k];
67             }
68         }
69         return up[a][0];
70     }
71 
72     int dist(int a, int b) const {
73         int L = lca(a, b);
74         return depth[a] + depth[b] - 2 * depth[L];
75     }
76 };
77 
78 int main() {
79     ios::sync_with_stdio(false);
80     cin.tie(nullptr);
81 
82     // Example tree:
83     // 1-2, 1-3, 2-4, 2-5, 3-6, 3-7, 6-8, 6-9
84     int n = 9;
85     LCA solver(n, 1);
86     vector<pair<int,int>> edges = {{1,2},{1,3},{2,4},{2,5},{3,6},{3,7},{6,8},{6,9}};
87     for (auto [u, v] : edges) solver.add_edge(u, v);
88     solver.build();
89 
90     cout << "LCA(4,5) = " << solver.lca(4,5) << "\n"; // 2
91     cout << "LCA(4,6) = " << solver.lca(4,6) << "\n"; // 1
92     cout << "kth_ancestor(9,1) = " << solver.kth_ancestor(9,1) << "\n"; // 6
93     cout << "kth_ancestor(9,3) = " << solver.kth_ancestor(9,3) << "\n"; // 3
94     cout << "dist(4,9) = " << solver.dist(4,9) << "\n"; // path length
95 
96     return 0;
97 }
98

This program builds a binary lifting table for a small tree, enabling O(log n) LCA, k-th ancestor, and distance queries. It uses BFS to compute depths and parents safely without recursion, fills the up table with the standard recurrence, and demonstrates multiple queries.

Time: Build: O(n log n), Query: O(log n)Space: O(n log n)

LCA with Path Sum and Max using Binary Lifting on Weighted Tree

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct LCAAgg {
5     int n, LOG, root;
6     vector<vector<int>> adj;
7     struct Edge { int to; long long w; };
8     vector<vector<Edge>> g;              // weighted adjacency
9     vector<int> depth;
10     vector<vector<int>> up;              // ancestors
11     vector<vector<long long>> sumUp;     // sum of weights along the 2^k jump
12     vector<vector<long long>> maxUp;     // max edge weight along the 2^k jump
13 
14     LCAAgg(int n_, int root_=1): n(n_), root(root_) {
15         LOG = 1; while ((1 << LOG) <= n) ++LOG;
16         g.assign(n + 1, {});
17         depth.assign(n + 1, 0);
18         up.assign(n + 1, vector<int>(LOG, 0));
19         sumUp.assign(n + 1, vector<long long>(LOG, 0));
20         maxUp.assign(n + 1, vector<long long>(LOG, LLONG_MIN));
21     }
22 
23     void add_edge(int u, int v, long long w) {
24         g[u].push_back({v, w});
25         g[v].push_back({u, w});
26     }
27 
28     void build() {
29         // BFS to set depth, up[v][0], and base aggregates
30         vector<int> vis(n + 1, 0);
31         queue<int> q;
32         vis[root] = 1; depth[root] = 0; up[root][0] = 0; sumUp[root][0] = 0; maxUp[root][0] = LLONG_MIN;
33         q.push(root);
34         while (!q.empty()) {
35             int v = q.front(); q.pop();
36             for (auto e : g[v]) if (!vis[e.to]) {
37                 vis[e.to] = 1;
38                 depth[e.to] = depth[v] + 1;
39                 up[e.to][0] = v;
40                 sumUp[e.to][0] = e.w;              // sum of edge to parent
41                 maxUp[e.to][0] = e.w;              // max of edge to parent
42                 q.push(e.to);
43             }
44         }
45         // DP for higher powers
46         for (int k = 1; k < LOG; ++k) {
47             for (int v = 1; v <= n; ++v) {
48                 int mid = up[v][k-1];
49                 if (mid == 0) {
50                     up[v][k] = 0;
51                     sumUp[v][k] = sumUp[v][k-1];   // lifting beyond root adds nothing
52                     maxUp[v][k] = maxUp[v][k-1];
53                 } else {
54                     up[v][k] = up[mid][k-1];
55                     sumUp[v][k] = sumUp[v][k-1] + sumUp[mid][k-1];
56                     maxUp[v][k] = max(maxUp[v][k-1], maxUp[mid][k-1]);
57                 }
58             }
59         }
60     }
61 
62     // Lift v by k steps, accumulating sum and max along the lifted path
63     int lift_with_agg(int v, int k, long long &sumAcc, long long &maxAcc) const {
64         for (int i = 0; i < LOG && v != 0; ++i) {
65             if (k & (1 << i)) {
66                 sumAcc += sumUp[v][i];
67                 maxAcc = max(maxAcc, maxUp[v][i]);
68                 v = up[v][i];
69             }
70         }
71         return v;
72     }
73 
74     int lca(int a, int b) const {
75         if (depth[a] < depth[b]) swap(a, b);
76         int d = depth[a] - depth[b];
77         long long s=0; long long m=LLONG_MIN; // ignored for pure LCA
78         a = lift_with_agg(a, d, s, m);
79         if (a == b) return a;
80         for (int k = LOG - 1; k >= 0; --k) {
81             if (up[a][k] != up[b][k]) {
82                 a = up[a][k];
83                 b = up[b][k];
84             }
85         }
86         return up[a][0];
87     }
88 
89     // Returns pair(sum, max) of edge weights along the path u -> v
90     pair<long long, long long> path_sum_max(int u, int v) const {
91         int L = lca(u, v);
92         long long sum1 = 0, sum2 = 0;
93         long long max1 = LLONG_MIN, max2 = LLONG_MIN;
94         // lift u up to L, and v up to L, accumulating aggregates
95         int du = depth[u] - depth[L];
96         int dv = depth[v] - depth[L];
97         int tmpu = u, tmpv = v;
98         lift_with_agg(tmpu, du, sum1, max1);
99         lift_with_agg(tmpv, dv, sum2, max2);
100         long long totalSum = sum1 + sum2;
101         long long totalMax = max(max1, max2);
102         // If u==v==L, max may remain LLONG_MIN; define it as 0 for empty path if needed
103         if (u == v) {
104             if (totalMax == LLONG_MIN) totalMax = 0;
105         }
106         return {totalSum, totalMax};
107     }
108 };
109 
110 int main() {
111     ios::sync_with_stdio(false);
112     cin.tie(nullptr);
113 
114     // Weighted tree example
115     // 1-2(3), 1-3(5), 2-4(2), 2-5(4), 3-6(7), 6-7(1)
116     int n = 7; LCAAgg S(n, 1);
117     S.add_edge(1,2,3); S.add_edge(1,3,5); S.add_edge(2,4,2); S.add_edge(2,5,4); S.add_edge(3,6,7); S.add_edge(6,7,1);
118     S.build();
119 
120     auto p1 = S.path_sum_max(4,5); // path: 4-2-5 (weights 2 + 4)
121     cout << "sum(4,5) = " << p1.first << ", max(4,5) = " << p1.second << "\n"; // 6, 4
122 
123     auto p2 = S.path_sum_max(4,7); // 4-2-1-3-6-7 (2+3+5+7+1)
124     cout << "sum(4,7) = " << p2.first << ", max(4,7) = " << p2.second << "\n"; // 18, 7
125 
126     return 0;
127 }
128

This program augments binary lifting with path aggregates: sum and max of edge weights. It stores for each node v and power k both the 2^k-th ancestor and the sum/max along that upward segment. Queries decompose the u→v path into u→L and v→L segments and combine their aggregates in O(log n).

Time: Build: O(n log n), Query: O(log n)Space: O(n log n) for ancestors + O(n log n) per stored aggregate

K-th Node on the Path between u and v using LCA

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct LCA {
5     int n, LOG, root;
6     vector<vector<int>> up;
7     vector<int> depth;
8     vector<vector<int>> g;
9 
10     LCA(int n_, int root_=1): n(n_), root(root_) {
11         LOG = 1; while ((1 << LOG) <= n) ++LOG;
12         up.assign(n + 1, vector<int>(LOG, 0));
13         depth.assign(n + 1, 0);
14         g.assign(n + 1, {});
15     }
16 
17     void add_edge(int u, int v) {
18         g[u].push_back(v);
19         g[v].push_back(u);
20     }
21 
22     void build() {
23         vector<int> vis(n + 1, 0);
24         queue<int> q;
25         vis[root] = 1; depth[root] = 0; up[root][0] = 0;
26         q.push(root);
27         while (!q.empty()) {
28             int v = q.front(); q.pop();
29             for (int to : g[v]) if (!vis[to]) {
30                 vis[to] = 1;
31                 depth[to] = depth[v] + 1;
32                 up[to][0] = v;
33                 q.push(to);
34             }
35         }
36         for (int k = 1; k < LOG; ++k)
37             for (int v = 1; v <= n; ++v) {
38                 int mid = up[v][k-1];
39                 up[v][k] = (mid ? up[mid][k-1] : 0);
40             }
41     }
42 
43     int lift(int v, int k) const {
44         for (int i = 0; i < LOG && v != 0; ++i)
45             if (k & (1 << i)) v = up[v][i];
46         return v;
47     }
48 
49     int lca(int a, int b) const {
50         if (depth[a] < depth[b]) swap(a, b);
51         a = lift(a, depth[a] - depth[b]);
52         if (a == b) return a;
53         for (int i = LOG - 1; i >= 0; --i)
54             if (up[a][i] != up[b][i]) { a = up[a][i]; b = up[b][i]; }
55         return up[a][0];
56     }
57 
58     // Returns the k-th node (0-indexed) on the path from u to v. k=0 -> u, k=dist(u,v) -> v.
59     int kth_on_path(int u, int v, int k) const {
60         int L = lca(u, v);
61         int du = depth[u] - depth[L]; // nodes from u down to L
62         if (k <= du) {
63             return lift(u, k);
64         } else {
65             int dv = depth[v] - depth[L];
66             int k2 = du + dv - k; // steps to move up from v to the target
67             return lift(v, k2);
68         }
69     }
70 };
71 
72 int main() {
73     ios::sync_with_stdio(false);
74     cin.tie(nullptr);
75 
76     // Tree: 1-2, 1-3, 2-4, 2-5, 3-6, 6-7
77     int n = 7; LCA T(n, 1);
78     vector<pair<int,int>> edges = {{1,2},{1,3},{2,4},{2,5},{3,6},{6,7}};
79     for (auto [u,v] : edges) T.add_edge(u,v);
80     T.build();
81 
82     int u = 4, v = 7;
83     int d = (T.depth[u] + T.depth[v] - 2 * T.depth[T.lca(u,v)]);
84     for (int k = 0; k <= d; ++k) {
85         cout << "k=" << k << ": node=" << T.kth_on_path(u, v, k) << "\n";
86     }
87 
88     return 0;
89 }
90

This code computes the k-th node on the path between two nodes using one LCA computation and up to two lifts. If k is within the segment from u to LCA, lift from u; otherwise, lift from v by the remaining steps. All operations are O(log n).

Time: Build: O(n log n), Each query: O(log n)Space: O(n log n)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct LCA {
5	int n, LOG;
6	int root;
7	vector<vector<int>> up; // up[v][k] = 2^k-th ancestor of v
8	vector<int> depth; // depth from root
9	vector<vector<int>> adj; // adjacency list (1-indexed)
10
11	LCA(int n_, int root_=1): n(n_), root(root_) {
12	LOG = 1;
13	while ((1 << LOG) <= n) ++LOG; // smallest LOG with 2^LOG > n
14	up.assign(n + 1, vector<int>(LOG, 0));
15	depth.assign(n + 1, 0);
16	adj.assign(n + 1, {});
17	}
18
19	void add_edge(int u, int v) {
20	adj[u].push_back(v);
21	adj[v].push_back(u);
22	}
23
24	void build() {
25	// BFS from root to set depth and first ancestors
26	queue<int> q;
27	vector<int> vis(n + 1, 0);
28	vis[root] = 1;
29	depth[root] = 0;
30	up[root][0] = 0; // parent of root is 0 (null)
31	q.push(root);
32	while (!q.empty()) {
33	int v = q.front(); q.pop();
34	for (int to : adj[v]) if (!vis[to]) {
35	vis[to] = 1;
36	depth[to] = depth[v] + 1;
37	up[to][0] = v; // parent
38	q.push(to);
39	}
40	}
41	// Build higher powers using DP
42	for (int k = 1; k < LOG; ++k) {
43	for (int v = 1; v <= n; ++v) {
44	int mid = up[v][k-1];
45	up[v][k] = (mid == 0 ? 0 : up[mid][k-1]);
46	}
47	}
48	}
49
50	int kth_ancestor(int v, int k) const {
51	// Returns the node k steps above v (k=0 returns v). Returns 0 if it does not exist.
52	for (int i = 0; i < LOG && v != 0; ++i) {
53	if (k & (1 << i)) v = up[v][i];
54	}
55	return v;
56	}
57
58	int lca(int a, int b) const {
59	if (depth[a] < depth[b]) swap(a, b);
60	int d = depth[a] - depth[b];
61	a = kth_ancestor(a, d);
62	if (a == b) return a;
63	for (int k = LOG - 1; k >= 0; --k) {
64	if (up[a][k] != up[b][k]) {
65	a = up[a][k];
66	b = up[b][k];
67	}
68	}
69	return up[a][0];
70	}
71
72	int dist(int a, int b) const {
73	int L = lca(a, b);
74	return depth[a] + depth[b] - 2 * depth[L];
75	}
76	};
77
78	int main() {
79	ios::sync_with_stdio(false);
80	cin.tie(nullptr);
81
82	// Example tree:
83	// 1-2, 1-3, 2-4, 2-5, 3-6, 3-7, 6-8, 6-9
84	int n = 9;
85	LCA solver(n, 1);
86	vector<pair<int,int>> edges = {{1,2},{1,3},{2,4},{2,5},{3,6},{3,7},{6,8},{6,9}};
87	for (auto [u, v] : edges) solver.add_edge(u, v);
88	solver.build();
89
90	cout << "LCA(4,5) = " << solver.lca(4,5) << "\n"; // 2
91	cout << "LCA(4,6) = " << solver.lca(4,6) << "\n"; // 1
92	cout << "kth_ancestor(9,1) = " << solver.kth_ancestor(9,1) << "\n"; // 6
93	cout << "kth_ancestor(9,3) = " << solver.kth_ancestor(9,3) << "\n"; // 3
94	cout << "dist(4,9) = " << solver.dist(4,9) << "\n"; // path length
95
96	return 0;
97	}
98

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct LCAAgg {
5	int n, LOG, root;
6	vector<vector<int>> adj;
7	struct Edge { int to; long long w; };
8	vector<vector<Edge>> g; // weighted adjacency
9	vector<int> depth;
10	vector<vector<int>> up; // ancestors
11	vector<vector<long long>> sumUp; // sum of weights along the 2^k jump
12	vector<vector<long long>> maxUp; // max edge weight along the 2^k jump
13
14	LCAAgg(int n_, int root_=1): n(n_), root(root_) {
15	LOG = 1; while ((1 << LOG) <= n) ++LOG;
16	g.assign(n + 1, {});
17	depth.assign(n + 1, 0);
18	up.assign(n + 1, vector<int>(LOG, 0));
19	sumUp.assign(n + 1, vector<long long>(LOG, 0));
20	maxUp.assign(n + 1, vector<long long>(LOG, LLONG_MIN));
21	}
22
23	void add_edge(int u, int v, long long w) {
24	g[u].push_back({v, w});
25	g[v].push_back({u, w});
26	}
27
28	void build() {
29	// BFS to set depth, up[v][0], and base aggregates
30	vector<int> vis(n + 1, 0);
31	queue<int> q;
32	vis[root] = 1; depth[root] = 0; up[root][0] = 0; sumUp[root][0] = 0; maxUp[root][0] = LLONG_MIN;
33	q.push(root);
34	while (!q.empty()) {
35	int v = q.front(); q.pop();
36	for (auto e : g[v]) if (!vis[e.to]) {
37	vis[e.to] = 1;
38	depth[e.to] = depth[v] + 1;
39	up[e.to][0] = v;
40	sumUp[e.to][0] = e.w; // sum of edge to parent
41	maxUp[e.to][0] = e.w; // max of edge to parent
42	q.push(e.to);
43	}
44	}
45	// DP for higher powers
46	for (int k = 1; k < LOG; ++k) {
47	for (int v = 1; v <= n; ++v) {
48	int mid = up[v][k-1];
49	if (mid == 0) {
50	up[v][k] = 0;
51	sumUp[v][k] = sumUp[v][k-1]; // lifting beyond root adds nothing
52	maxUp[v][k] = maxUp[v][k-1];
53	} else {
54	up[v][k] = up[mid][k-1];
55	sumUp[v][k] = sumUp[v][k-1] + sumUp[mid][k-1];
56	maxUp[v][k] = max(maxUp[v][k-1], maxUp[mid][k-1]);
57	}
58	}
59	}
60	}
61
62	// Lift v by k steps, accumulating sum and max along the lifted path
63	int lift_with_agg(int v, int k, long long &sumAcc, long long &maxAcc) const {
64	for (int i = 0; i < LOG && v != 0; ++i) {
65	if (k & (1 << i)) {
66	sumAcc += sumUp[v][i];
67	maxAcc = max(maxAcc, maxUp[v][i]);
68	v = up[v][i];
69	}
70	}
71	return v;
72	}
73
74	int lca(int a, int b) const {
75	if (depth[a] < depth[b]) swap(a, b);
76	int d = depth[a] - depth[b];
77	long long s=0; long long m=LLONG_MIN; // ignored for pure LCA
78	a = lift_with_agg(a, d, s, m);
79	if (a == b) return a;
80	for (int k = LOG - 1; k >= 0; --k) {
81	if (up[a][k] != up[b][k]) {
82	a = up[a][k];
83	b = up[b][k];
84	}
85	}
86	return up[a][0];
87	}
88
89	// Returns pair(sum, max) of edge weights along the path u -> v
90	pair<long long, long long> path_sum_max(int u, int v) const {
91	int L = lca(u, v);
92	long long sum1 = 0, sum2 = 0;
93	long long max1 = LLONG_MIN, max2 = LLONG_MIN;
94	// lift u up to L, and v up to L, accumulating aggregates
95	int du = depth[u] - depth[L];
96	int dv = depth[v] - depth[L];
97	int tmpu = u, tmpv = v;
98	lift_with_agg(tmpu, du, sum1, max1);
99	lift_with_agg(tmpv, dv, sum2, max2);
100	long long totalSum = sum1 + sum2;
101	long long totalMax = max(max1, max2);
102	// If u==v==L, max may remain LLONG_MIN; define it as 0 for empty path if needed
103	if (u == v) {
104	if (totalMax == LLONG_MIN) totalMax = 0;
105	}
106	return {totalSum, totalMax};
107	}
108	};
109
110	int main() {
111	ios::sync_with_stdio(false);
112	cin.tie(nullptr);
113
114	// Weighted tree example
115	// 1-2(3), 1-3(5), 2-4(2), 2-5(4), 3-6(7), 6-7(1)
116	int n = 7; LCAAgg S(n, 1);
117	S.add_edge(1,2,3); S.add_edge(1,3,5); S.add_edge(2,4,2); S.add_edge(2,5,4); S.add_edge(3,6,7); S.add_edge(6,7,1);
118	S.build();
119
120	auto p1 = S.path_sum_max(4,5); // path: 4-2-5 (weights 2 + 4)
121	cout << "sum(4,5) = " << p1.first << ", max(4,5) = " << p1.second << "\n"; // 6, 4
122
123	auto p2 = S.path_sum_max(4,7); // 4-2-1-3-6-7 (2+3+5+7+1)
124	cout << "sum(4,7) = " << p2.first << ", max(4,7) = " << p2.second << "\n"; // 18, 7
125
126	return 0;
127	}
128