Lowest Common Ancestor II
View as PDFProblem Statement
You are given a tree with vertices. The tree is rooted at
.
You are also given queries, each containing two integers
and
representing vertices of the tree. For each query you should output the lowest common ancestor of
and
using an Euler Tour.
Use the following template for a sparse table to get the index of the minimum value in an array.
class SparseTable:
def __init__(self, arr):
self.arr = arr
self.n = len(arr)
self.log = [0] * (self.n + 1)
self._compute_logs()
self.st = self._build_sparse_table()
def _compute_logs(self):
for i in range(2, self.n + 1):
self.log[i] = self.log[i // 2] + 1
def _build_sparse_table(self):
k = self.log[self.n] + 1
st = [[(0, 0)] * k for _ in range(self.n)]
for i in range(self.n):
st[i][0] = (self.arr[i], i)
j = 1
while (1 << j) <= self.n:
i = 0
while (i + (1 << j) - 1) < self.n:
if st[i][j - 1][0] < st[i + (1 << (j - 1))][j - 1][0]:
st[i][j] = st[i][j - 1]
else:
st[i][j] = st[i + (1 << (j - 1))][j - 1]
i += 1
j += 1
return st
def query(self, L, R):
j = self.log[R - L + 1]
if self.st[L][j][0] < self.st[R - (1 << j) + 1][j][0]:
return self.st[L][j]
else:
return self.st[R - (1 << j) + 1][j]
# example use:
arr = [1, 3, -1, 7, 0, 5, 8, 6, 2, -4]
sparse_table = SparseTable(arr)
# get the minimum value in the subarray from 2 to 7
min_value, min_index = sparse_table.query(2, 7)
print(f"Minimum value: {min_value}, Index: {min_index}")
NOTE: The lowest common ancestor of two vertices, and
, in a rooted tree, is the deepest node which is along the root to leaf path of both
and
.
Input Format
Your first line will contain two space-separated integers and
.
Your next
lines will contain two space-separated integers each
and
representing an edge from
to
.
Your next
lines will contain two space-separated integers each,
and
representing the vertices for which you would like to find the lowest common ancestor.
Output Format
For each of the queries, you should output the LCA for the given nodes.
Constraints
and
## Template
import sys
sys.setrecursionlimit(int(1e9))
n, q = map(int, input().split())
edges = [map(int, input().split()) for _ in range(n - 1)]
queries = [map(int, input().split()) for _ in range(q)]
# REMEMBER TO PASTE SPARSE TABLE TEMPLATE HERE
# print your output
Sample Cases
Input 1
5 5
1 2
2 3
2 4
1 5
2 5
5 2
3 4
2 3
4 4Output 1
1
1
2
2
4Input 2
10 10
4 7
7 8
2 4
6 7
8 10
5 8
2 9
3 7
1 9
2 9
6 8
8 9
2 8
8 9
3 8
4 10
5 7
5 6
3 9Output 2
9
7
9
2
9
7
4
7
7
9
Comments