Binary Lifting Guide for Competitive Programming

Binary Lifting is a Dynamic Programming approach for trees where we precompute some ancestors of every node. It is used to answer a large number of queries where in each query we need to find an arbitrary ancestor of any node in a tree in logarithmic time.

The idea behind Binary Lifting:

1. Preprocessing in Binary Lifting:

In preprocessing, we initialize the ancestor[][] table, such that ancestor[i][j] stores the 2^jth ancestor of node i.

• Initially, we set all the cells of ancestor[][] table = -1.
• Run a DFS to initialize the immediate parent, that is we initialize ancestor[i][0] for all the nodes.
• Now, we have initialized the first column of our ancestor table. For all the remaining columns, we can use the following recursive formula,

ancestor[i][j] = ancestor[ancestor[i][j-1]][j-1], when ancestor[i][j-1] != -1

The idea is that we can reach (2^j)^th ancestor of node i, by making 2 jumps of size (2^(j-1)), that is (2^j) = (2^(j-1)) + (2^(j-1)). After the first jump from node i, we will reach ancestor[i][j-1] and after the 2nd jump from node ancestor[i][j-1], we will reach ancestor[ancestor[i][j-1]][j-1]

2. Handling Queries in Binary Lifting:

Let's say we need to find 100^th ancestor of node X, but in the ancestor[][] table we only have 1^st, 2^nd, 4^th, 8^th, 16^th, 32^nd, 64^th, 128^th .... ancestors of the current node. Now, we will jump to the maximum possible ancestor such that we don't exceed the 100th ancestor (Safe Jump). So, we will jump to the 64^th ancestor of the current node. Now, the problem is reduced to finding the (100-64) = 36^th ancestor of this node. We can again jump to the maximum possible ancestor which does not exceed 36, that is 32. We keep on doing this till we reach the required node. In order to find the next safe jump, we can use the binary representation of K. Move from the most significant bit to least significant bit and for every set bit j, we take a jump from this node to the (2^j)^th ancestor of the node, which is already stored in ancestor[i][j].

For 100th ancestor of node X,
(100)₁₀ = (1100100)₂

So, to calculate 100^th ancestor of Node X,
Move to 64^th ancestor of X = ancestor[X][6] = A₁
Then, to calculate the 36^th ancestor of A₁,
Move to the 32^nd ancestor of A₁ = ancestor[A₁][5] = A₂
Then, to calculate the 4^th ancestor of A₂,
Move to the 4^th ancestor of A₂ = ancestor[A₂][2] = A₃

Implementation of Binary Lifting:

#include <bits/stdc++.h> using namespace std; // Depth First Search void dfs(int node, vector<vector<int> >& graph,  vector<vector<int> >& ancestor, int parent) {  ancestor[node][0] = parent;  for (int neighbor : graph[node]) {  dfs(neighbor, graph, ancestor, node);  } } // Method to initialize ancestor table void preprocess(vector<vector<int> >& graph,  vector<vector<int> >& ancestor, int V,  int maxN) {  dfs(1, graph, ancestor, -1);  for (int j = 1; j < maxN; j++) {  for (int i = 1; i <= V; i++) {  if (ancestor[i][j - 1] != -1)  ancestor[i][j]  = ancestor[ancestor[i][j - 1]][j - 1];  }  } } // Method to find Kth ancestor of node int findKthAncestor(vector<vector<int> >& ancestor,  int node, int K, int maxN) {  for (int i = maxN - 1; i >= 0; i--) {  if (K & (1 << i)) {  if (ancestor[node][i] == -1)  return -1;  node = ancestor[node][i];  }  }  return node; } int main() {  int V = 7;  int maxN = log2(V) + 1;  // edge list  vector<vector<int> > edges  = { { 1, 2 }, { 1, 3 }, { 3, 4 },  { 4, 5 }, { 4, 6 }, { 5, 7 } };  vector<vector<int> > graph(V + 1),  ancestor(V + 1, vector<int>(maxN, -1));  // construct the adjacency list  for (auto edge : edges) {  graph[edge[0]].push_back(edge[1]);  }  // preprocessing  preprocess(graph, ancestor, V, maxN);  // queries  cout << findKthAncestor(ancestor, 7, 3, maxN) << "\n";  cout << findKthAncestor(ancestor, 5, 1, maxN) << "\n";  cout << findKthAncestor(ancestor, 7, 4, maxN) << "\n";  cout << findKthAncestor(ancestor, 6, 4, maxN) << "\n";  return 0; } 

import java.util.*; import java.lang.*; class GFG {  // Depth First Search  static void dfs(int node, List<List<Integer>> graph, List<List<Integer>> ancestor, int parent) {  ancestor.get(node).set(0, parent);  for (int neighbor : graph.get(node)) {  dfs(neighbor, graph, ancestor, node);  }  }  // Method to initialize ancestor table  static void preprocess(List<List<Integer>> graph, List<List<Integer>> ancestor, int V, int maxN) {  dfs(1, graph, ancestor, -1);  for (int j = 1; j < maxN; j++) {  for (int i = 1; i <= V; i++) {  if (ancestor.get(i).get(j - 1) != -1)  ancestor.get(i).set(j, ancestor.get(ancestor.get(i).get(j - 1)).get(j - 1));  }  }  }  // Method to find Kth ancestor of node  static int findKthAncestor(List<List<Integer>> ancestor, int node, int K, int maxN) {  for (int i = maxN - 1; i >= 0; i--) {  if ((K & (1 << i)) != 0) {  if (ancestor.get(node).get(i) == -1)  return -1;  node = ancestor.get(node).get(i);  }  }  return node;  }  public static void main (String[] args) {  int V = 7;  int maxN = (int) (Math.log(V) / Math.log(2)) + 1;  // edge list  List<List<Integer>> edges = Arrays.asList(  Arrays.asList(1, 2), Arrays.asList(1, 3), Arrays.asList(3, 4),  Arrays.asList(4, 5), Arrays.asList(4, 6), Arrays.asList(5, 7)  );  List<List<Integer>> graph = new ArrayList<>();  List<List<Integer>> ancestor = new ArrayList<>();    for (int i = 0; i <= V; i++) {  graph.add(new ArrayList<>());  ancestor.add(new ArrayList<>(Collections.nCopies(maxN, -1)));  }  // construct the adjacency list  for (List<Integer> edge : edges) {  graph.get(edge.get(0)).add(edge.get(1));  }  // preprocessing  preprocess(graph, ancestor, V, maxN);  // queries  System.out.println(findKthAncestor(ancestor, 7, 3, maxN));  System.out.println(findKthAncestor(ancestor, 5, 1, maxN));  System.out.println(findKthAncestor(ancestor, 7, 4, maxN));  System.out.println(findKthAncestor(ancestor, 6, 4, maxN));  } } 

import math # Depth First Search def dfs(node, graph, ancestor, parent): ancestor[node][0] = parent for neighbor in graph[node]: dfs(neighbor, graph, ancestor, node) # Method to initialize ancestor table def preprocess(graph, ancestor, V, maxN): dfs(1, graph, ancestor, -1) for j in range(1, maxN): for i in range(1, V + 1): if ancestor[i][j - 1] != -1: ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1] # Method to find Kth ancestor of node def find_kth_ancestor(ancestor, node, K, maxN): for i in range(maxN - 1, -1, -1): if K & (1 << i): if ancestor[node][i] == -1: return -1 node = ancestor[node][i] return node if __name__ == "__main__": V = 7 maxN = int(math.log2(V)) + 1 # edge list edges = [[1, 2], [1, 3], [3, 4], [4, 5], [4, 6], [5, 7]] graph = [[] for _ in range(V + 1)] ancestor = [[-1] * maxN for _ in range(V + 1)] # construct the adjacency list for edge in edges: graph[edge[0]].append(edge[1]) # preprocessing preprocess(graph, ancestor, V, maxN) # queries print(find_kth_ancestor(ancestor, 7, 3, maxN)) print(find_kth_ancestor(ancestor, 5, 1, maxN)) print(find_kth_ancestor(ancestor, 7, 4, maxN)) print(find_kth_ancestor(ancestor, 6, 4, maxN)) 

using System; using System.Collections.Generic; class Program {  static void dfs(int node, List<List<int>> graph, List<List<int>> ancestor, int parent)  {  ancestor[node][0] = parent;  foreach (int neighbor in graph[node])  {  dfs(neighbor, graph, ancestor, node);  }  }  static void preprocess(List<List<int>> graph, List<List<int>> ancestor, int V, int maxN)  {  dfs(1, graph, ancestor, -1);  for (int j = 1; j < maxN; j++)  {  for (int i = 1; i <= V; i++)  {  if (ancestor[i][j - 1] != -1)  {  ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1];  }  }  }  }  static int findKthAncestor(List<List<int>> ancestor, int node, int K, int maxN)  {  for (int i = maxN - 1; i >= 0; i--)  {  if ((K & (1 << i)) != 0)  {  if (ancestor[node][i] == -1)  return -1;  node = ancestor[node][i];  }  }  return node;  }  static void Main()  {  int V = 7;  int maxN = (int)Math.Log(2, V) + 1;  // edge list  List<List<int>> edges = new List<List<int>>  {  new List<int> { 1, 2 },  new List<int> { 1, 3 },  new List<int> { 3, 4 },  new List<int> { 4, 5 },  new List<int> { 4, 6 },  new List<int> { 5, 7 }  };  List<List<int>> graph = new List<List<int>>(V + 1);  List<List<int>> ancestor = new List<List<int>>(V + 1);  for (int i = 0; i <= V; i++)  {  graph.Add(new List<int>());  ancestor.Add(new List<int>(new int[maxN]));  }  // construct the adjacency list  foreach (List<int> edge in edges)  {  graph[edge[0]].Add(edge[1]);  }  // preprocessing  preprocess(graph, ancestor, V, maxN);  // queries  Console.WriteLine(findKthAncestor(ancestor, 7, 3, maxN));  Console.WriteLine(findKthAncestor(ancestor, 5, 1, maxN));  Console.WriteLine(findKthAncestor(ancestor, 7, 4, maxN));  Console.WriteLine(findKthAncestor(ancestor, 6, 4, maxN));  } } 

// Depth First Search function dfs(node, graph, ancestor, parent) {  ancestor[node][0] = parent;  for (let neighbor of graph[node]) {  dfs(neighbor, graph, ancestor, node);  } } // Method to initialize ancestor table function preprocess(graph, ancestor, V, maxN) {  dfs(1, graph, ancestor, -1);  for (let j = 1; j < maxN; j++) {  for (let i = 1; i <= V; i++) {  if (ancestor[i][j - 1] !== -1)  ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1];  }  } } // Method to find Kth ancestor of node function findKthAncestor(ancestor, node, K, maxN) {  for (let i = maxN - 1; i >= 0; i--) {  if (K & (1 << i)) {  if (ancestor[node][i] === -1)  return -1;  node = ancestor[node][i];  }  }  return node; } // Main function function main() {  let V = 7;  let maxN = Math.floor(Math.log2(V)) + 1;  // edge list  let edges = [  [1, 2], [1, 3], [3, 4],  [4, 5], [4, 6], [5, 7]  ];  let graph = Array.from({ length: V + 1 }, () => []);  let ancestor = Array.from({ length: V + 1 }, () => Array(maxN).fill(-1));  // construct the adjacency list  for (let edge of edges) {  graph[edge[0]].push(edge[1]);  }  // preprocessing  preprocess(graph, ancestor, V, maxN);  // queries  console.log(findKthAncestor(ancestor, 7, 3, maxN));  console.log(findKthAncestor(ancestor, 5, 1, maxN));  console.log(findKthAncestor(ancestor, 7, 4, maxN));  console.log(findKthAncestor(ancestor, 6, 4, maxN)); } // Run the main function main(); 

3 4 1 -1

Time Complexity: O(N*log(N) + Q*log(N)), where N is the number of nodes and Q is the number of queries.
Space Complexity: O(N*logN)

Why to use Binary Lifting?

Suppose we have a tree with N number of nodes, and we need to answer queries Q, wherein for each query we need to find an arbitrary ancestor of any node, we can solve it using the following techniques:

• We can run a DFS and maintain a parent array par[], such that par[i] stores the immediate parent of node i. Now, if we need to calculate the Kth ancestor of any node, we run a loop K times and in each loop, we move to the parent of the current node and after K iterations, we will have our Kth ancestor. This way, we need to run a loop for every query, so the overall time complexity will be O(Q * N), which is quite inefficient.
• We can pre-compute all the ancestors of every node in a 2D array ancestor[N][N], such that ancestor[i][j] will store the jth ancestor of node i. This precomputation will take O(N * N + Q) time and O(N*N) space but after the precomputation, we can answer every query in O(1) time. This approach is useful when the number of queries is quite large as compared to the number of nodes but if the number of nodes is in the range 10^5, then this approach will exceed the time limit.
• Instead of precomputing all the ancestors of every node, we can store some specific ancestors of every node. We can maintain a 2D array ancestor[N][logN+1], such that ancestor[i][j] stores the (2 ^ j)th ancestor of node i. Since for each node we are only storing those ancestors which are perfect powers of 2, the space and time complexity to precompute the ancestor table will be reduced to O(N * logN) but to answer each query we will need O(logN) time. So, the overall time complexity will be O(N * logN + Q * log)

Use Cases of Binary Lifting:

1. To calculate arbitrary Ancestor node of any node:

Binary Lifting is used to answer a large number of queries such that in each query we need to calculate an arbitrary ancestor of any node. We have already covered this in the above implementation.

2. To calculate the Lowest Common Ancestor (LCA) of two nodes in a tree:

Binary Lifting is also used to calculate the Lowest Common Ancestor of 2 nodes in a tree. Refer this article to know about calculating LCA using Binary Lifting.

3. To calculate path aggregates in a tree:

Binary Lifting is also used to extract information about the paths in a tree. This can be done by altering the ancestor[][] table by storing extra information in it. Suppose we are given a weighted tree and Q queries. In each query, we are given 2 nodes (X and Y) and we need to find the maximum of all the edges which lie in the path from X to Y. We can solve this problem by storing additional information in the ancestor[][] table. Earlier, ancestor[i][j] stores only (2^j)^th ancestor of node i, now we will also store the maximum of all the edges which lie in the path when we jump from node i to (2^j)^th node. Now, to calculate the answer, we find the LCA(X, Y) and then divide the path into 2 parts: Path from node X to LCA(X, Y) and Path from LCA(X, Y) to node Y. Now, we return the maximum of both the paths.

Implementation:

#include <bits/stdc++.h> using namespace std; int maxN = 31; // Depth First Search void dfs(int node, vector<vector<pair<int, int> > >& graph,  vector<vector<pair<int, int> > >& ancestor,  vector<int>& level) {  for (pair<int, int> edge : graph[node]) {  int neighbor = edge.first;  int weight = edge.second;  ancestor[neighbor][0].first = node;  ancestor[neighbor][0].second = weight;  level[neighbor] = level[node] + 1;  dfs(neighbor, graph, ancestor, level);  } } // Method to initialize ancestor table void preprocess(vector<vector<pair<int, int> > >& graph,  vector<vector<pair<int, int> > >& ancestor,  vector<int>& level, int V) {  dfs(1, graph, ancestor, level);  for (int j = 1; j < maxN; j++) {  for (int i = 1; i <= V; i++) {  int ancestorNode = ancestor[i][j - 1].first;  if (ancestorNode != -1) {  ancestor[i][j].first  = ancestor[ancestorNode][j - 1].first;  ancestor[i][j].second = max(  ancestor[i][j - 1].second,  ancestor[ancestorNode][j - 1].second);  }  }  } } // Method to find LCA of two nodes int findLCA(vector<vector<pair<int, int> > >& ancestor,  vector<int>& level, int X, int Y) {  if (level[X] < level[Y])  swap(X, Y);  int diff = level[X] - level[Y];  for (int i = maxN; i >= 0; i--) {  if (diff & (1 << i)) {  diff -= (1 << i);  X = ancestor[X][i].first;  }  }  if (X == Y)  return X;  for (int i = maxN; i >= 0; i--) {  if (ancestor[X][i].first != -1  && ancestor[X][i].first  != ancestor[Y][i].first) {  X = ancestor[X][i].first;  Y = ancestor[Y][i].first;  }  }  return ancestor[X][0].first; } // Method to get max edge weight between a node // and its ancestor int getMaxEdge(vector<vector<pair<int, int> > >& ancestor,  vector<int>& level, int X, int Y) {  int maxEdge = 0;  if (level[X] < level[Y])  swap(X, Y);  int diff = level[X] - level[Y];  for (int i = maxN; i >= 0; i--) {  if (diff & (1 << i)) {  diff -= (1 << i);  maxEdge = max(maxEdge, ancestor[X][i].second);  X = ancestor[X][i].first;  }  }  return maxEdge; } // Method to get max edge weight between 2 nodes int findMaxWeight(  vector<vector<pair<int, int> > >& ancestor,  vector<int>& level, int X, int Y) {  int LCA = findLCA(ancestor, level, X, Y);  // Max edge weight from node X to LCA  int path1 = getMaxEdge(ancestor, level, X, LCA);  // Max edge weight from LCA to node Y  int path2 = getMaxEdge(ancestor, level, Y, LCA);  // Return maximum of both paths  return max(path1, path2); } int main() {  int V = 7;  // edge list  vector<vector<int> > edges  = { { 1, 2, 6 }, { 1, 3, 3 }, { 3, 4, 4 },  { 4, 5, 2 }, { 4, 6, 1 }, { 5, 7, 5 } };  vector<vector<pair<int, int> > > graph(V + 1);  // ancestor[i][j].first = (2^j)th ancestor of node i  // ancestor[i][j].second = max edge weight which lies  // in the path from node i to (2^j)th ancestor of node i  vector<vector<pair<int, int> > > ancestor(  V + 1, vector<pair<int, int> >(maxN, { -1, 0 }));  // vector to store level of nodes  vector<int> level(V + 1, 0);  // construct the adjacency list  for (auto edge : edges) {  graph[edge[0]].push_back({ edge[1], edge[2] });  }  // preprocessing  preprocess(graph, ancestor, level, V);  // queries  for (int i = 1; i <= V; i++) {  for (int j = 1; j <= V; j++)  cout << findMaxWeight(ancestor, level, i, j)  << " ";  cout << "\n";  }  return 0; } 

import java.util.*; public class LCA_MaxEdgeWeight {  static int maxN = 31;  // Depth First Search to populate ancestor and level arrays  static void dfs(int node, List<List<int[]>> graph, int[][][] ancestor, int[] level) {  for (int[] edge : graph.get(node)) {  int neighbor = edge[0];  int weight = edge[1];  // Set the (2^0)th ancestor and its weight for the neighbor  ancestor[neighbor][0][0] = node;  ancestor[neighbor][0][1] = weight;  level[neighbor] = level[node] + 1;  dfs(neighbor, graph, ancestor, level);  }  }  // Perform preprocessing to fill the ancestor table  static void preprocess(List<List<int[]>> graph, int[][][] ancestor, int[] level, int V) {  dfs(1, graph, ancestor, level);  for (int j = 1; j < maxN; j++) {  for (int i = 1; i <= V; i++) {  int ancestorNode = ancestor[i][j - 1][0];  if (ancestorNode != -1) {  // Calculate the (2^j)th ancestor and its weight  ancestor[i][j][0] = ancestor[ancestorNode][j - 1][0];  ancestor[i][j][1] = Math.max(ancestor[i][j - 1][1], ancestor[ancestorNode][j - 1][1]);  } else {  ancestor[i][j][0] = -1; // Mark as invalid ancestor  }  }  }  }  // Find the Lowest Common Ancestor of two nodes X and Y  static int findLCA(int[][][] ancestor, int[] level, int X, int Y) {  if (level[X] < level[Y]) {  int temp = X;  X = Y;  Y = temp;  }  int diff = level[X] - level[Y];  for (int i = 0; i < maxN; i++) {  if (((diff >> i) & 1) == 1) {  diff -= (1 << i);  X = ancestor[X][i][0];  }  }  if (X == Y) {  return X;  }  for (int i = maxN - 1; i >= 0; i--) {  if (ancestor[X][i][0] != -1 && ancestor[X][i][0] != ancestor[Y][i][0]) {  X = ancestor[X][i][0];  Y = ancestor[Y][i][0];  }  }  return ancestor[X][0][0];  }  // Get the maximum edge weight between a node and its ancestor  static int getMaxEdge(int[][][] ancestor, int[] level, int X, int Y) {  int maxEdge = 0;  if (level[X] < level[Y]) {  int temp = X;  X = Y;  Y = temp;  }  int diff = level[X] - level[Y];  for (int i = 0; i < maxN; i++) {  if (((diff >> i) & 1) == 1) {  diff -= (1 << i);  maxEdge = Math.max(maxEdge, ancestor[X][i][1]);  X = ancestor[X][i][0];  }  }  return maxEdge;  }  // Find the maximum edge weight between two nodes X and Y  static int findMaxWeight(int[][][] ancestor, int[] level, int X, int Y) {  int LCA = findLCA(ancestor, level, X, Y);  int path1 = getMaxEdge(ancestor, level, X, LCA);  int path2 = getMaxEdge(ancestor, level, Y, LCA);  return Math.max(path1, path2);  }  public static void main(String[] args) {  int V = 7;  int[][] edges = {{1, 2, 6}, {1, 3, 3}, {3, 4, 4}, {4, 5, 2}, {4, 6, 1}, {5, 7, 5}};  List<List<int[]>> graph = new ArrayList<>();  for (int i = 0; i <= V; i++) {  graph.add(new ArrayList<>());  }  // Construct the adjacency list  for (int[] edge : edges) {  graph.get(edge[0]).add(new int[]{edge[1], edge[2]});  }  int[][][] ancestor = new int[V + 1][maxN][2];  for (int i = 0; i <= V; i++) {  for (int j = 0; j < maxN; j++) {  Arrays.fill(ancestor[i][j], -1);  }  }  int[] level = new int[V + 1];  // Preprocess the data  preprocess(graph, ancestor, level, V);  // Queries  for (int i = 1; i <= V; i++) {  for (int j = 1; j <= V; j++) {  System.out.print(findMaxWeight(ancestor, level, i, j) + " ");  }  System.out.println();  }  } } //This code is contribuyted by Adarsh. 

maxN = 31 def dfs(node, graph, ancestor, level): # Depth First Search to populate ancestor and level arrays for edge in graph[node]: neighbor, weight = edge # Set the (2^0)th ancestor and its weight for the neighbor ancestor[neighbor][0] = (node, weight) level[neighbor] = level[node] + 1 dfs(neighbor, graph, ancestor, level) def preprocess(graph, ancestor, level, V): # Perform preprocessing to fill the ancestor table dfs(1, graph, ancestor, level) for j in range(1, maxN): for i in range(1, V + 1): ancestorNode = ancestor[i][j - 1][0] if ancestorNode != -1: # Calculate the (2^j)th ancestor and its weight ancestor[i][j] = (ancestor[ancestorNode][j - 1][0], max(ancestor[i][j - 1][1], ancestor[ancestorNode][j - 1][1])) def findLCA(ancestor, level, X, Y): # Find the Lowest Common Ancestor of two nodes X and Y if level[X] < level[Y]: X, Y = Y, X diff = level[X] - level[Y] for i in range(maxN): if diff & (1 << i): diff -= (1 << i) X = ancestor[X][i][0] if X == Y: return X for i in range(maxN): if ancestor[X][i][0] != -1 and ancestor[X][i][0] != ancestor[Y][i][0]: X = ancestor[X][i][0] Y = ancestor[Y][i][0] return ancestor[X][0][0] def getMaxEdge(ancestor, level, X, Y): # Get the maximum edge weight between a node and its ancestor maxEdge = 0 if level[X] < level[Y]: X, Y = Y, X diff = level[X] - level[Y] for i in range(maxN): if diff & (1 << i): diff -= (1 << i) maxEdge = max(maxEdge, ancestor[X][i][1]) X = ancestor[X][i][0] return maxEdge def findMaxWeight(ancestor, level, X, Y): # Find the maximum edge weight between two nodes X and Y LCA = findLCA(ancestor, level, X, Y) path1 = getMaxEdge(ancestor, level, X, LCA) path2 = getMaxEdge(ancestor, level, Y, LCA) return max(path1, path2) V = 7 edges = [[1, 2, 6], [1, 3, 3], [3, 4, 4], [4, 5, 2], [4, 6, 1], [5, 7, 5]] graph = [[] for _ in range(V + 1)] ancestor = [[(-1, 0) for _ in range(maxN)] for _ in range(V + 1)] level = [0] * (V + 1) # Construct the adjacency list for edge in edges: graph[edge[0]].append((edge[1], edge[2])) # Preprocess the data preprocess(graph, ancestor, level, V) # Queries for i in range(1, V + 1): for j in range(1, V + 1): print(findMaxWeight(ancestor, level, i, j), end=" ") print() 

using System; class Program {  static int maxN = 31;  static void Dfs(int node, Tuple<int, int>[][] graph,  Tuple<int, int>[][] ancestor, int[] level)  {  foreach (var edge in graph[node])  {  int neighbor = edge.Item1;  int weight = edge.Item2;  ancestor[neighbor][0] = Tuple.Create(node, weight);  level[neighbor] = level[node] + 1;  Dfs(neighbor, graph, ancestor, level);  }  }  static void Preprocess(Tuple<int, int>[][] graph,  Tuple<int, int>[][] ancestor,  int[] level, int V)  {  for (int i = 1; i <= V; i++)  {  ancestor[i] = new Tuple<int, int>[maxN];  for (int j = 0; j < maxN; j++)  {  ancestor[i][j] = Tuple.Create(-1, 0);  }  }  Dfs(1, graph, ancestor, level);  for (int j = 1; j < maxN; j++)  {  for (int i = 1; i <= V; i++)  {  int ancestorNode = ancestor[i][j - 1].Item1;  if (ancestorNode != -1)  {  ancestor[i][j] = Tuple.Create(  ancestor[ancestorNode][j - 1].Item1,  Math.Max(ancestor[i][j - 1].Item2,  ancestor[ancestorNode][j - 1].Item2));  }  }  }  }  static int FindLca(Tuple<int, int>[][] ancestor,  int[] level, int X, int Y)  {  if (level[X] < level[Y])  (X, Y) = (Y, X);  int diff = level[X] - level[Y];  for (int i = maxN - 1; i >= 0; i--)  {  if ((diff & (1 << i)) != 0)  {  diff -= (1 << i);  X = ancestor[X][i].Item1;  }  }  if (X == Y)  return X;  for (int i = maxN - 1; i >= 0; i--)  {  if (ancestor[X][i].Item1 != -1 &&  ancestor[X][i].Item1 != ancestor[Y][i].Item1)  {  X = ancestor[X][i].Item1;  Y = ancestor[Y][i].Item1;  }  }  return ancestor[X][0].Item1;  }  static int GetMaxEdge(Tuple<int, int>[][] ancestor,  int[] level, int X, int Y)  {  int maxEdge = 0;  if (level[X] < level[Y])  (X, Y) = (Y, X);  int diff = level[X] - level[Y];  for (int i = maxN - 1; i >= 0; i--)  {  if ((diff & (1 << i)) != 0)  {  diff -= (1 << i);  maxEdge = Math.Max(maxEdge, ancestor[X][i].Item2);  X = ancestor[X][i].Item1;  }  }  return maxEdge;  }  static int FindMaxWeight(Tuple<int, int>[][] ancestor,  int[] level, int X, int Y)  {  int LCA = FindLca(ancestor, level, X, Y);  int path1 = GetMaxEdge(ancestor, level, X, LCA);  int path2 = GetMaxEdge(ancestor, level, Y, LCA);  return Math.Max(path1, path2);  }  static void Main(string[] args)  {  int V = 7;  int[][] edges = {  new int[] {1, 2, 6},  new int[] {1, 3, 3},  new int[] {3, 4, 4},  new int[] {4, 5, 2},  new int[] {4, 6, 1},  new int[] {5, 7, 5}  };  var graph = new Tuple<int, int>[V + 1][];  for (int i = 0; i <= V; i++)  {  graph[i] = new Tuple<int, int>[0];  }  var ancestor = new Tuple<int, int>[V + 1][];  var level = new int[V + 1];  foreach (var edge in edges)  {  int from = edge[0];  int to = edge[1];  int weight = edge[2];  Array.Resize(ref graph[from], graph[from].Length + 1);  graph[from][graph[from].Length - 1] = Tuple.Create(to, weight);  }  Preprocess(graph, ancestor, level, V);  for (int i = 1; i <= V; i++)  {  for (int j = 1; j <= V; j++)  {  Console.Write(FindMaxWeight(ancestor, level, i, j) + " ");  }  Console.WriteLine();  }  } }